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

https://leetcode.com/problems/find-kth-bit-in-nth-binary-string/description/

leetcode - Find Kth Bit in Nth Binary String

문제 유형: 비트 조작, 재귀, 문자열 처리

문제 난이도: Medium

 

문제

Given two positive integers n and k, the binary string Sn is formed as follows:

• S1 = "0"
• Si = Si - 1 + "1" + reverse(invert(Si - 1)) for i > 1

Where + denotes the concatenation operation, reverse(x) returns the reversed string x, and invert(x) inverts all the bits in x (0 changes to 1 and 1 changes to 0).

For example, the first four strings in the above sequence are:

• S1 = "0"
• S2 = "011"
• S3 = "0111001"
• S4 = "011100110110001"

Return the kth bit in Sn. It is guaranteed that k is valid for the given n.

 

두 개의 정수 n과 k가 주어진다. 바이너리 문자열 S_n은 다음과 같은 형태를 가진다:

S₁ = "0"

S_i = S_i-1 + "1 " + reverse(invert(S_i-1)) for i > 1이다.

 

+는 접합 연산자, reverse(x)는 비트문자열 x를 뒤집는 함수, invert(x)는 비트플립 함수이다.

 

Sn에서 k번째 비트를 구하시오. 항상 유효한 인풋이 주어집니다.

 

풀이

재귀로 범위를 좁혀가면서 해결할 수 있다.

만약 n이 1이면, '0'을 반환한다.

 

아니라면, 다음의 과정을 따른다:

문자열의 길이를 구한다. 문자열의 길이는 len = 2^n-1이다.

len = (1 << n) -1로 빠르게 구할 수 있다.

중앙 인덱스는 (len+1) /2이다.

 

만약 k가 중앙이면, "1"을 반환하라.

만약 k가 중앙보다 작으면, findKthBit(n-1, k)을 반환한다.

만약 k가 중앙보다 크다면, 문자열 뒤집기와 비트플립을 고려해서, 새로운 인덱스로 호출한다.

  findKthBit(n-1, len-k+1)을 호출하면, 문자열 뒤집기를 고려한 호출이고, 이 값에 대해 비트플립을 해주면 된다.

 

 

코드

C++

class Solution {
public:
    char findKthBit(int n, int k) {
        if(n == 1) return '0';

        int len = (1 << n) - 1;
        int mid = ((len+1)/2);

        if(k == mid) return '1';
        else if(k < mid) {
            return findKthBit(n-1, k);
        } else {
            char res = findKthBit(n-1, len-k+1);
            return (res == '0')?'1':'0';
        }
    }
};