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

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/148652

프로그래머스

정답 코드

def solution(n, l, r):
    def calSquare(number):
        square = 0
        while number:
            square += 1
            number //= 5
        return square
    
    squareL = calSquare(l-1)
    squareR = calSquare(r)
    
    def countOne(number, square):
        cnt = 0
        while number:
            tmp = 5 ** square
            share = number // tmp
            remainder = number % tmp
            if share > 2:
                cnt += (share - 1) * 4 ** square
            elif share < 2:
                cnt += share * 4 ** square
            else:
                cnt += share * 4 ** square
                remainder = 0
            
            if remainder < 6:
                if remainder > 2:
                    cnt += remainder - 1
                else:
                    cnt += remainder
                break

            number = remainder
            square -= 1
        return cnt
    
    cntL = countOne(l-1, squareL)
    cntR = countOne(r, squareR)
    answer = cntR - cntL
    return answer

풀이 방법

n	유사 칸토어	규칙	1의 개수
0	1	1	1
1	11011	1 1 0 1 1	4
2	1101111011000001101111011	4 4 0 4 4	16
3	1101111011000001101111011 110111101100000110111101100000000000000000000000 1101111011000001101111011 1101111011000001101111011	16 16 0 16 16	64

1. 위와 같이 전체 1의 개수를 유추할 수 있다.
2. 계산식이 복잡하여 이미지로 보도록 하자

• 몫이 2일 때 나머지를 버리는 이유는 몫이 2일 때 0만 있는 위치에 해당하기 때문이다.
• 몫이 3일 때는 0만 있는 위치를 빼기 때문에 몫에서 1을 빼준다.

느낀점

• 규칙을 알면 그나마 쉽게 풀리는 문제