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

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 = 2,5,17 
# result = 8

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

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

print(solution(n, l, r))

 

다른 코드로도 시도해보았지만 답은 나와도 시간복잡도에서 걸려서 생각해본 방법이다.

 

재귀함수로 조건을 위와 같이 만들어주면 해당 인덱스의 자리값이 나온다.

시간 복잡도에서도 살짝 위험하지만 통과한다.

그런나 이방법은 효율적이지 않다. 일반화를 하면 더 효율적으로 풀 수 있는 방법이 있다.

 

칸토어 비트열의 특징은 수열의 길이가 5**n 형태라는 것. 5진수 형태로 나타내면 특징이 보인다

n=2 인 칸토어 비트열을 한번 출력했을 때

첫번째는 칸토어 비트열

두번째는 인덱스

세번째는 5진수로 치환했을때의 값이다.

 

직접 출력해보면 확실히 특징이 보인다. 5진수로 나타냈을 때 한 자리라도 2가 들어가면 0, 나머지는 1이다.

그리고 n번째 칸토어 비트열의 합은 4**n 이기 때문에 5진수로 나타냈을 때 각 자리는

4**(n-1), 4**(n-2), 4**(n-2)를 나타냄을 알 수 있다. 이 정보들을 가지고 코드를 만들어보면

 

# 5진수를 만드는 함수
def dec_to_pen(n,sum=''):
    if n==0: 
        if sum=='': sum='0'
        return sum
    return dec_to_pen(n//5,str(n%5)+sum)

# i까지의 칸토어 비트열의 합을 구하는 함수 
def cantor(i):
    # 이 조건이 중요하다 i가 -1일 경우도 있기 때문
    if i <0: 
        return 0
    arr = [1,1,0,1,1]
    sum_cantor = 0
    penta = dec_to_pen(i)
    # 2가 오른쪽에서 처음 시작하는 인덱스 찾기, 없다면 len(penta)
    find_2 = len(penta)-penta.find('2')-1
    # 5진수에서 합 구하기
    for idx, j in enumerate(penta[::-1]):
        if idx==0 and find_2==len(penta):
            sum_cantor += sum(arr[:int(j)+1])
        elif find_2==len(penta) or idx>=find_2:
            sum_cantor += sum(arr[:int(j)])*(4**(idx))
    return sum_cantor
    
def solution(n, l, r):
    answer=cantor(r-1)-cantor(l-2)
    return answer

 

시간복잡도 O(k)로 풀 수 있게된다.

 

 

사실 이렇게 풀고 기분좋아져서 다른 사람들 풀이 보니깐 역시 코딩이나 수학 잘하는 사람들은 많다는 것을 느꼈다..

더 열심히 해야겠다.