[알고리즘/Python] 유사 칸토어 비트열

문제

프로그래머스 - 유사 칸토어 비트열
🔂 문제 링크입니다! 🔂

문제 풀이

유사 칸토어 비트열의 길이가 5의 N승으로 늘어나기 때문에 처음 문제를 보고 겁을 먹을 수 있겠습니다.(저요)
하지만 우리가 필요한 것은 해당 구간 내에서 1의 갯수이기 때문에, 수열에서 0이 등장하는 경우만 제외시켜주면 됩니다.

저는 땅굴을 깊게 파다가 아래 블로그에서 도움을 받았습니다. 감사합니다.

다시 문제 분석으로 돌아가보자면, 우리가 무시해야하는 경우인 0의 위치에 주목해서 인덱스를 확인해보았습니다.

비트열의 길이가 5의 제곱으로 늘어나므로 5진수를 이용해서 깔끔하게 정리할 수 있었습니다.
위의 친절한 설명을 보시면 0은 5자리 숫자 중 무조건 가운데, 즉 2번째 자리에 등장하는 것을 볼 수 있습니다.
천천히 살펴보니 0의 위치를 5진수로 바꾼 값에는 2가 들어가있습니다.
그럼 저희는 인덱스를 5진수로 바꾸면서 나머지나 마지막 몫에 2가 있는지만 확인하면 해당 위치에 0이 있는지, 1이 있는지 확인할 수 있을 것입니다.👍

여기에서 잠깐, 10진수를 어떻게 5진수로 만드냐구요?

타단.. 이렇게 10진수를 5로 나누지 못할 때까지 나눠줍니다. 나눌때마다 옆에 나머지들을 적어주고, 몫이 5보다 작아서 더이상 나누지 못할 경우 몫부터 나머지들을 거꾸로 읽어줍니다. 그럼 5진수가 나옵니다.

간단한 알고리즘 시나리오는 다음과 같습니다.

cnt는 1의 개수를 저장합니다.
1. l~r까지 반복문을 돌면서 십진수를 5진수로 변환한다.
2. 변환 과정에서 나머지 혹은 마지막 몫이 2가 나오는 경우가 있다면, 0이 있는 것이므로 무시한다.
3. 모든 경우에 2가 나오지 않는다면, 1이 있는 것이다. cnt를 1 증가시킨다.
4. 모든 반복문을 다 돈 후, cnt를 반환한다.

소스 코드

위의 시나리오를 파이선 코드로 옮기면 다음과 같습니다.

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

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