유사 칸토어 비트열

수학에서 칸토어 집합은 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]을 나타냅니다.

---

입출력 예

nlrresult

2

4

17

8

---

입출력 예 설명

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

 

프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

나의 풀이

# 2024-08-09
# 동적 프로그래밍 인가??.. 일단 무지성 ㄱㄱ
def solution(n, l, r):
    answer = 0
    
    cantou = '1'
    for _ in range(n):
        cantou = cantou.replace('0','00000')
        cantou = cantou.replace('1','11011')

    answer = cantou[l-1:r].count('1')
    return answer

• 역시 시간 초과.. 칸토어 비트열이 커질수롤 5**n 씩 문자열이 길어지므로 비효율적임..

 

수정코드

# 2024-08-09
# 규칙
# [1], [11011], [1101111011000001101111011] 
# 그럼 0의 인덱스는?? what?????
# [없음], [2], [2,7,10,11,12,13,14,17,22]
# 아닛!! 두둥 해당 인덱스의 5진수로 변환시 2가 포함되면 0이다!!!!!! 이런이런
# 그럼 이제 구현 해보자
def five_jinsu(num):
    while True:
        if num%5==2:
            return False
        num=num//5
        if num==0:
            break
    return True

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

• 인덱스를 5진수로 변환시 2가 포함되면 0인 규칙을 발견후 구현

통과!!!