파이썬으로 n번째 이진 문자열에서 k번째 비트 찾기

문제 소개

두 개의 양수 n과 k가 주어졌을 때, 다음 규칙에 따라 이진 문자열 S_n을 만들 수 있다고 가정해 보겠습니다.

S₁ = 0
i > 1인 경우, S_i = S_i-1 + "1" + reverse(invert(S_i-1))

여기서 reverse(x)는 문자열 x를 거꾸로 뒤집은 결과를 반환하고, invert(x)는 x의 모든 비트를 반전합니다(0은 1로, 1은 0으로).

이 규칙으로 만들어진 처음 네 개의 문자열은 다음과 같습니다.

S₁ = "0"
S₂ = "011"
S₃ = "0111001"
S₄ = "011100110110001"

구해야 하는 것은 S_n에서 k번째 비트의 값입니다.

예를 들어 입력이 n = 4, k = 10이라면 출력은 1입니다. S₄ = "011100110110001"에서 10번째 비트가 1이기 때문입니다(첫 번째 비트의 위치를 1로 계산).

해결 접근 방법

k가 1이면 어떤 문자열이든 첫 번째 비트는 항상 0이므로 바로 "0"을 반환하면 됩니다. 그 외의 경우에는 필요한 길이에 도달할 때까지 문자열을 단계별로 확장해 나가는 방식을 사용합니다.

핵심은 두 개의 배열을 함께 관리하는 것입니다.

arr: 현재 단계의 이진 문자열에 해당하는 배열
arr2: arr을 비트 반전한 뒤 거꾸로 뒤집은 값, 즉 reverse(invert(arr))를 저장하는 배열

arr의 길이가 k보다 작은 동안 아래 과정을 반복합니다.

templast := arr의 복사본
temp2last := arr2의 복사본
arr := templast + [1] + temp2last
arr2 := templast + [0] + temp2last

반복이 끝나면 arr의 (k−1)번째 요소가 곧 정답이 됩니다.

예제 코드

def solve(n, k):
    if k == 1:
        return(str(0))
    else:
        arr = [0]
        arr2 = [1]
        while k > len(arr):
            templast = arr.copy()
            temp2last = arr2.copy()
            arr = templast + [1] + temp2last
            arr2 = templast + [0] + temp2last
        return(str(arr[k-1]))

n = 4
k = 10
print(solve(n, k))

입력

4, 10

출력

동작 원리

각 단계에서 새 문자열의 길이는 '이전 길이 × 2 + 1'이 됩니다. 따라서 S₁의 길이는 1, S₂는 3, S₃은 7, S₄는 15이며, 일반적으로 S_i의 길이는 2ⁱ − 1입니다.

코드에서 arr2는 항상 reverse(invert(arr))라는 성질을 유지합니다. 그래서 다음 단계의 문자열을 만들 때 이 값을 그대로 뒤에 붙이기만 하면 되고, 매번 새로 반전·역순 연산을 수행할 필요가 없습니다. 이 덕분에 로직이 단순해지고, 시간 복잡도는 목표 위치 k에 비례하는 O(k) 수준으로 유지됩니다.