[LeetCode] 1545 - Find Kth Bit in Nth Binary String

문제

• 링크: https://leetcode.com/problems/find-kth-bit-in-nth-binary-string
• 난이도: Medium
• 태그: 문자열, 재귀, 시뮬레이션
• 결과: Time: 51 ms (27.86%), Space: 33.6 MB (42.69%)

풀이

class Solution {
public:
    char findKthBit(int n, int k) {
        vector<char> v;
        v.emplace_back('0');
        for (int itr = 2; itr <= n; ++itr)
        {
            int ti = v.size();
            v.emplace_back('1');
            for (int i = 0; i < ti; ++i)
            {
                v.emplace_back(v[ti - i - 1] == '1' ? '0' : '1');
            }
        }

        return v[k - 1];
    }
};

n이 충분히 작아서 직접 만들어서 반환하게끔 구현했다. 1ms를 사용한 Code Sample도 구경해봤는데, 아래와 같았다.

class Solution {
public:
    char findKthBit(int n, int k) {
        // Base case: When n = 1, the binary string is "0"
        if (n == 1) return '0';
        
        // Find the length of the current string Sn, which is 2^n - 1
        int length = (1 << n) - 1;
        
        // Find the middle position
        int mid = length / 2 + 1;
        
        // If k is the middle position, return '1'
        if (k == mid) return '1';
        
        // If k is in the first half, find the bit in Sn-1
        if (k < mid) return findKthBit(n - 1, k);
        
        // If k is in the second half, find the bit in Sn-1 and invert it
        return findKthBit(n - 1, length - k + 1) == '0' ? '1' : '0';
    }
};

재귀를 통해 구현하는 것으로, 각 라인별 설명은 주석에 충분히 설명되어 있다. 직접 만드는 것보다 더 단순하게, 규칙을 찾아 간단하게 구현할 수 있을 거라고 생각은 했지만 이렇게 재귀로 깔끔하게 풀릴거라고 생각하진 못했다. 그야말로, ‘깔끔한’ 풀이다!

배운 점과 후기

Editorial에 O(1) 풀이가 있다. 읽어보면 공포스러울 지경이다…