LeetCode - 1980. Find Unique Binary String

문제링크

 

문제 설명

길이가 n인 고유한 이진 문자열 n개가 담긴 문자열 배열 nums가 주어집니다.

이때, nums에 존재하지 않는 길이 n의 이진 문자열을 반환하세요.

만약 가능한 정답이 여러 개라면, 그중 아무 것이나 반환해도 됩니다.

 

제한 사항

• n == nums.length
• 1 <= n <= 16
• nums[i].length == n
• nums[i]는 '0' 또는 '1'로만 구성됩니다.
• nums의 모든 문자열은 서로 고유(unique) 합니다.

 

예시

Example 1:

Input: nums = ["01","10"]
Output: "11"
Explanation: "11" does not appear in nums. "00" would also be correct.

 

Example 2:

Input: nums = ["00","01"]
Output: "11"
Explanation: "11" does not appear in nums. "10" would also be correct.

 

Example 3:

Input: nums = ["111","011","001"]
Output: "101"
Explanation: "101" does not appear in nums. "000", "010", "100", and "110" would also be correct.

 

풀이 흐름

• n의 범위가 16이므로 최대로 탐색해야 될 경우의 수는 2^16 = 65,536이기 때문에 백트래킹으로 전체를 탐색해도 시간 초과가 발생하지 않겠다고 판단했습니다.
• 백트래킹으로 이진 문자열을 만들면서 문자열의 길이가 n이 될 경우 nums안에 포함이 되는지 파악했습니다.
  • 만약 nums안에 없을 경우 해당 문자열이 정답 중 하나이므로 바로 반환했습니다.
  • 만약 nums안에 있을 경우 null을 반환하였고 return 받는 곳에서도 null을 return 받으면 백트래킹을 이어가도록 구현했습니다.

 

코드

import java.util.*;

class Solution {
    public String findDifferentBinaryString(String[] nums) {
        int N = nums[0].length();
        Set<String> set = new HashSet<>();
        for (String num : nums) {
            set.add(num);
        }
        return dfs(set, "", 0, N);
    }

    private String dfs(Set<String> set, String num, int d, int N) {
        if (d == N) {
            if (set.contains(num)) {
                return null;
            }
            return num;
        }
        String[] tmp = {"0", "1"};
        for (int i = 0; i < tmp.length; i++) {
            String res = dfs(set, num + tmp[i], d + 1, N);
            if (res != null) {
                return res;
            }
        }
        return null;
    }
}