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

1. 개요

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

2. 재귀호출 풀이

def solution(n, l, r):
    # l과 r사이의 구간에서의 1의 갯수는
    # r까지의 1의 갯수에서 l-1까지의 1의갯수를 뺀것이다.
    return oneCount(r)-oneCount(l-1)

def oneCount(n):
    # 남은 숫자가 5이하일경우 1의 갯수를 그냥 구한다.
    if n <= 5:
        return '11011'[:n].count('1')

    # n보다 작거나 같은 최대의 5의 제곱수를 구한다.
    # 그리로 부터 5토막을 내는 단위(divider), 한토막당 1의 갯수를 구할수 있다.
    curPower = getPowerOfFive(n)
    divider, sectionOneCount = 5**(curPower), 4**(curPower)
    mock, remain = n//divider, n%divider
    result = mock*sectionOneCount

    # 2토막이면 바로 갯수를 반환한다.
    # 3토막 이상이면 3토막째에는 1의 갯수가 0이므로, 한토막당 1의갯수를 빼줘야 한다.
    if mock==2:
        return result
    if mock>=3:
        result -= sectionOneCount
    
    # 토막을 내고 남은 숫자에 대해서 다시 5토막을 내서 재귀적으로 답을 구한다.
    if remain:
        return result + oneCount(remain)
    else:
        return result
            
def getPowerOfFive(num):
    power = 1
    while 5**(power+1) < num:
        power += 1
    return power