[프로그래머스] 유사 칸토어 비트열 Lv. 2 Python

문제 링크

1. 문제 설명

수학에서 칸토어 집합은 0과 1 사이의 실수로 이루어진 집합으로, [0, 1]부터 시작하여 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만들어집니다.

남아는 칸토어 집합을 조금 변형하여 유사 칸토어 비트열을 만들었습니다. 유사 칸토어 비트열은 다음과 같이 정의됩니다.

0 번째 유사 칸토어 비트열은 "1" 입니다.
n(1 ≤ n) 번째 유사 칸토어 비트열은 n - 1 번째 유사 칸토어 비트열에서의 1을 11011로 치환하고 0을 00000로 치환하여 만듭니다.
남아는 n 번째 유사 칸토어 비트열에서 특정 구간 내의 1의 개수가 몇 개인지 궁금해졌습니다.
n과 1의 개수가 몇 개인지 알고 싶은 구간을 나타내는 l, r이 주어졌을 때 그 구간 내의 1의 개수를 return 하도록 solution 함수를 완성해주세요.

2. 문제 접근

n번째 유사 칸토어 비트열을 생성하기는 어렵지 않습니다. 문제는 칸토어 비트열의 길이가 기하급수적으로 커진다는 데 있습니다. 첫 번째 비트열의 길이는 5, 두 번째는 25.. 최대 n = 20이므로 최악의 경우 $5^{20}\approx10^{14}$의 계산을 해야 합니다. 이는 비효율적이며 수열에서 0이 등장하는 규칙을 이해한다면 전혀 필요없는 작업입니다.

0번째 비트열은 '1'이고 첫번째 비트열은 '11011'입니다.
두 번째 비트열은 어떻게 생성이 될까요? '11011'이 두 번, '00000'이 한 번, '11011'이 두 번 더해져 다음과 같이 생성됩니다.

11011 - 11011 - 00000 - 11011 - 11011

0의 위치에 주목해서 인덱스를 확인해 봅시다. 위 수열에서 0의 인덱스는 [2, 7 ,10~14, 17, 22] 입니다. 이를 세 자리의 5진수로 바꾸면 [002, 012, 020~024, 032, 042]가 됩니다.

n=3일때 0이 어떻게 생성될지 생각해 봅시다. 우선 숫자 한 개가 5개의 숫자로 치환되므로 수열의 길이가 5배가 됩니다. 또한 치환 전 숫자 0이 0이 5개로 치환되므로 위에서 찾은 0의 인덱스를 활용할 수 있습니다. [002] 인덱스의 0에 들어온 5개의 0의 인덱스는 [0020 ~ 0024] 가 됩니다. 비슷하게 [0120~0124, 0200~0244 .. ] 등이 0의 인덱스입니다. 원래 1이 있던 인덱스에는 숫자 5개가 들어와 가운데 하나가 0이 됩니다. [000]의 1이 있던 자리에 [0000~ 0004] 5개가 들어오고 그 중 0의 인덱스는 [0002] 입니다.

0의 패턴이 보이시나요? 인덱스를 5진수로 치환했을 때 단 한 자리수라도 2를 포함한다면 0의 인덱스가 됩니다. 이는 인덱스를 5로 계속 나누면서 나머지가 2가 되는 경우가 한 번이라도 있으면 해당됩니다. 따라서 시작, 끝 인덱스가 주어지면 그 사이 0의 개수를 쉽게 확인할 수 있습니다.

3. 문제 풀이

def solution(n, l, r):
    answer = 0
    for l in range(l-1, r):
        if is_one(l):
            answer += 1
    return answer

def is_one(l):
    while l >= 5:
        if (l - 2) % 5 == 0:
            return False
        l //= 5

    return l != 2