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

문제 정보

제목 : 유사 칸토어 비트열

난이도 : Lv.2

사용 언어 : Python

문제 링크

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

프로그래머스

 

문제 설명

수학에서 칸토어 집합은 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 함수를 완성해주세요.

 

제한 사항

• 1 ≤ n ≤ 20
• 1 ≤ l, r ≤ 5n
  • l ≤ r < l + 10,000,000
  • l과 r은 비트열에서의 인덱스(1-base)이며 폐구간 [l, r]을 나타냅니다.

입출력 예

n	l	r	result
2	4	17	8

 

입출력 예 설명

2 번째 유사 칸토어 비트열은 "1101111011000001101111011" 입니다. 음영 표시된 부분은 폐구간 [4, 17] 이며 구간 내의 1은 8개 있습니다.

---

나의 풀이

11011의 위치를 0부터 4로 잡으면 0은 항상 5*n + 2의 위치에 해당합니다. 그렇게 해서 특정 숫자 i를 5로 나누었을때 나머지가 2라면 해당 숫자는 0이므로 0을 리턴합니다. 그리고 i가 5보다 작다면 1을 return합니다. 이외의 숫자는 나머지를 버리면서 둘 중 하나의 조건이 만족할 때까지 재귀적으로 실행합니다.

위의 함수를 l-1부터 r까지 반복하는 for루프를 이용해 1이 return되면 answer을 1 더합니다.

 

코드

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

def cantor(i) :
    if( i % 5 == 2):
        return 0
    if( i < 5 ):
        return 1
    return cantor(i // 5)