[LeetCode] 1980. Find Unique Binary String

https://leetcode.com/problems/find-unique-binary-string/description/

Find Unique Binary String - LeetCode

leetcode - Find Unique Binary String

문제 유형 : 비트마스킹, 비트 조작, 수학, 정렬, DFS, 백트래킹, 트라이(Trie)

문제 난이도 : Medium

 

문제

Given an array of strings nums unique binary strings each of length n, return a binary string of length n that does not appear in nums. If there are multiple answers, you may return any of them.

 

n짜리의 길이의 중복되지 않은 이진 바이너리 문자열이 있는 배열 nums가 주어진다.

nums에 없는 이진 바이너리 문자열을 반환하라.

값이 여러 개일수 있으니, 하나만 반환하면 된다.

 

풀이

바이너리 문자열을 오름차순 정렬한 것과 이 바이너리들을 정수로 만들었을 때의 순서는 같다.

카운트로 0부터 배열에서 없는 바이너리인지 찾아가면서 중간에 빠진 바이너리를 찾으면 n의 길이에 맞추어 반환하면 된다.

배열을 다 돌고 나서도 그냥 카운트를 바이너리 문자열로 바꾸면 된다.

 

이 외에도 백트래킹을 이용하거나,

nums[i][i]의 비트와 다른 비트를 추가해가면서 새로운 비트를 생성하는 법(무조건 다른 비트 만드는법)이 있는데,

정렬을 이용하는 방법이 스스로 생각해내서 좋았다.

 

 

코드

C++ - 정렬을 이용한 방법

class Solution {
public:
    int btoi(string num) {
        int count = 0;
        long n = stol(num);
        int sum = 0;

        while(n > 0) {
            if(n%10 == 1) sum += pow(2, count);
            n /= 10;
            count++;
        }

        return sum;
    }

    string itob(int number, int size) {
        bitset<32> bits(number);

        string bitString = bits.to_string();
        return bitString.substr(32-size, size);
    }

    string findDifferentBinaryString(vector<string>& nums) {
        sort(nums.begin(), nums.end());
        const int bitsize = nums[0].size();

        int cnt = 0;
        for(const auto &num : nums) {
            //cout << btoi(num) << " " << cnt << endl;
            if(btoi(num) != cnt) break;
            cnt++;
        }

        return itob(cnt, bitsize);
    }
};

 

 

C++ - 중복되지 않을 문자열을 생성하기

class Solution {
public:
    string findDifferentBinaryString(vector<string>& nums) {
        string str;

        for (int i = 0; i < nums.size(); ++i) {
            str += (nums[i][i] == '0' ? '1' : '0');
        }

        return str;
    }
};