1545. Find Kth Bit in Nth Binary String

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

 

Difficulty : Medium

 

Status : Solved

 

Time : 00:08:05

 

---

 

문제 설명

 

 

두 개의 양의 정수 n, k가 주어질 때, Sn은 다음과 같이 형성된다.

 

• S1 = "0"
• i > 1 일때 Si = S(i-1) + "1" + reverse(invert(S(i-1)))

 

+는 연결 연산자이다. reverse(x)는 문자열 x를 뒤집은 결과를 반환한다. invert(x)는 x의 모든 비트를 뒤집는다(0은 1로, 1은 0으로)

예를 들어, 위의 순서대로 맨 처음 4개의 문자열은 다음과 같다 :

 

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

Sn의 k번째 비트를 반환하라. 주어진 n 내에서 k는 유효함이 보장된다.

---

 

풀이

 

수열의 특성을 생각해보자. 우리는 조합 (n, k)의 해답을 찾는다고 가정한다.

 

우선, Sn은 무조건 길이가 2 ^ n - 1개의 길이를 가진다. 그리고 그 가운데(즉 2^(n-1)번째, mid라 칭하자.)는 "1"로 구성된다. 이 가운데를 기준으로, 왼쪽은 S(n-1) 문자열이고, 오른쪽은 reverse(invert(S(n-1)))가 될 것이다.

 

• 주어진 k가 정확히 mid이라면, 그냥 1을 반환하면 된다.
• 주어진 k가 왼쪽에 있다면, (n-1, k)의 결과를 반환하면 된다.
• 주어진 k가 오른쪽에 있다면...
  • 기본적으로 S(n-1)번째 결과물을 변형한 결과가 될 것이다. 즉 (n-1, ?)의 결과를 가공하는 형태가 될 것이다.
  • reverse 결과를 생각해보자. (2^n - 1 - mid)번째 숫자는 mid + 1번째... 이런 식으로 뒤집히게 된다. (n, k)는 (n-1, k - mid)와 대응되게 될 것이므로, 제대로 된 결과를 얻으려면 k - mid가 reverse 전후로 어떻게 변화하는지 살펴보면 된다. 그 결과는 (2^n - mid) - (k - mid) = (2 ^ n - k)가 될 것이고, 우리는 (n-1, 2 ^ n - k)의 결과를 우선 취하도록 한다.
  • inverse 결과는 단순히 0을 1로, 1을 0으로 변환하면 되므로, 앞서 구한 (n-1, 2 ^ n - k)의 결과를 뒤집으면 된다.

이런 식으로, 재귀적으로 풀 수 있다. O(n) 시간복잡도 내로 풀 수 있으며, n의 최대 크기 자체가 얼마 크지 않으므로 매우 빠르게 계산 결과가 나온다.

 

 

풀이 코드

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        if n == k == 1 :
            return "0"
        l = 2 ** (n - 1)
        if l == k :
            return "1"
        if l > k :
            return self.findKthBit(n-1, k)
        return "1" if self.findKthBit(n-1, 2 ** n - k) == "0" else "0"