프로그래머스 유사 칸토어 비트열

문제

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

프로그래머스

 

풀이

i번째 칸토어 비트열의 길이와 1의 갯수를 구한다.

A = [(1,1)] # 1의갯수,길이
for i in range(1,n + 1):
    p1,p2 = A[-1]
    A.append((p1*4,p2*5))

 

구하려는 구간이 (l,r)이다.

1. (l,r) 안에 i번째 칸토어 비트열이 온전히 존재한다면,

i번째 칸토어 비트열의 1의 개수를 정답에 더해주고 해당 비트열을 더 나눌 필요가 없다.

 

2. 엄청 나게 긴 i번째 비트열을 생각해보자.

만약에 비트열의 시작이 l보다 작고 끝이 r보다 크다면 i번째 비트열을 i-1번째 비트열 5개로 나눠줘야한다.

1~5번째 비트열중 3번째 비트열은 0으로 채워져있을 것이다. 따라서 목적과 관계없다.

x번재 비트열의 끝이 l보다 작거나 시작이 r보다 크다면 우리가 구하려는 구간을 벗어난 것이므로 관계없다.

def solution(n, l, r):
    # 1 -> 11011
    # 0 -> 00000
    # i번째 비트열의 1의갯수와 길이를 구하기
    A = [(1,1)]
    for i in range(1,n + 1):
        p1,p2 = A[-1]
        A.append((p1*4,p2*5))
    oneCnt,start,end,idx = A[-1][0],1,A[-1][1],len(A)-1
    stack = [(oneCnt,start,end,idx)]
    ans = 0 # 정답
    while stack:
        num,left,right,idx = stack.pop() # 현재 비트열의 1의개수,구간시작,구간끝,몇번째 비트열인지
        if l <= left and right <= r: # 비트열이 온전
            ans += num # 1의 개수를 더해줌
        else:
            # 5개로 나누기
            x,y = A[idx-1]
            for i in range(5):
                z,w = left + i*y,left + (i+1)*y - 1 # 나눠진 비트열의 구간
                if w < l or z > r: # 만약에 구하려는 구간에 포함안되는 비트열이면 패스
                    continue
                if i == 2: # 가운데 비트열은 0으로 채워지므로 패스
                    continue
                stack.append((x,z,w,idx-1))      
    return ans