[LeetCode] 1980 - Find Unique Binary String

2026.03.08

문제

링크: https://leetcode.com/problems/find-unique-binary-string
난이도: Medium
태그: 배열, 해시 테이블, 문자열
결과: Time: 0 ms (100%), Space: 8.3 MB (10.47%)

풀이

나의 풀이

class Solution {
public:
    string findDifferentBinaryString(vector<string>& nums) {
        set<uint16_t> s;
        for (int i = 0; i < nums.size(); ++i)
        {
            string str = nums[i];
            uint16_t dec = strToDec(str);
            s.insert(dec);
        }

        uint16_t found = 0;
        for (int i = 0; i < 65535; ++i)
        {
            if(!s.contains(i))
            {
                found = i;
                break;
            }
        }

        return decToStr(found, nums.size());
    }

    uint16_t strToDec(string& s)
    {
        uint16_t dec = 0;
        int len = s.size();
        for (int i = 0; i < len; ++i)
        {
            dec <<= 1;
            if(s[i] == '1')
            {
                dec |= 1;
            }
        }

        return dec;
    }

    string decToStr(uint16_t n, int len)
    {
        vector<char> tmp;
        for(uint16_t i = 1 << 15; i > 0; i >>= 1)
        {
            tmp.push_back((n & i) ? '1' : '0');
        }

        string sub(tmp.begin() + (16 - len), tmp.end());
        return sub;
    }
};

그냥 시키는대로 했다…

내가 잘못 생각한 부분

일단 두 번째 루프에서 num을 n까지만 증가시키는데, 나는 이 역할을 하는 루프가 65535까지 증가한다. 문제의 조건에 따라 집합에는 수가 최대 n개 밖에 없으므로 n + 1개 중 적어도 하나는 반드시 집합에 없게 된다. 따라서, 0 ~ n 범위만 찾아보면 무조건 답이 나온다.

Editorial 코드 1

나는 다 직접 구현했는데, Editorial에서는 훨씬 더 간단하게 구현한게 있었다.

class Solution {
public:
    string findDifferentBinaryString(vector<string>& nums) {
        unordered_set<int> integers;
        for (string num : nums) {
            integers.insert(stoi(num, 0, 2));
        }
        
        int n = nums.size();
        for (int num = 0; num <= n; num++) {
            if (integers.find(num) == integers.end()) {
                string ans = bitset<16>(num).to_string();
                return ans.substr(16 - n);
            }
        }
        
        return "";
    }
};

stoi

두 번째 인자가 index고 세 번째 인자가 base다. 2진수도 변환할 수 있는지 몰랐다.

std::bitset

사실 이 클래스 잘 모른다. 그래서 찾아봤다. bitset은 고정 크기 N의 비트 배열을 다루는 컨테이너이다.

| 메서드 | 설명 | 예시 결과 | | ————– | ———– | ———— | | .to_string() | 비트를 문자열로 변환 | "00000110" | | .to_ulong() | 비트를 정수로 변환 | 6 | | .count() | 1인 비트 개수 | 2 | | .size() | 전체 비트 크기 | 8 | | [i] | i번째 비트 접근 | b[1] == 1 |

Editorial 코드 2

class Solution {
public:
    string findDifferentBinaryString(vector<string>& nums) {
        string ans;
        for (int i = 0; i < nums.size(); i++) {
            char curr = nums[i][i];
            ans += curr == '0' ? '1' : '0';
        }
        
        return ans;
    }
};

O(N)으로 푸는 코드이다. 칸토어의 대각선 논법을 활용한다. i번째 이진수에 대해 i번째 자리를 뒤집어서 새로운 이진수를 만든다. 그러면 입력으로 주어진 모든 이진수와 다르지만 길이는 같은 출력을 얻을 수 있는 것이다!

문제에서 문자열의 개수 = 문자열의 길이 = n으로 동일하므로 가능한 풀이이다. 만약 문자열의 길이 < n이었다면 인덱스 범위를 초과했을 것이다.

배운 점과 후기

bitset에 대해서 배웠고, O(N) 풀이의 흥미로운 직관을 엿볼 수 있었다.

주휘중