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

문제 바로가기

문제 설명

수학에서 칸토어 집합은 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. 재귀함수를 통한 칸토어 비트열 함수 정의

def Cantor(n):
    if n == 0:
        return '1'
    beatstring = ''
    for i in Cantor(n-1):
        if i == '1':
            beatstring += '11011'
        if i == '0':
            beatstring += '00000'
    return beatstring

def solution(n, l, r):
    answer = 0
    string = Cantor(n)
    for x in Cantor(n)[l-1:r]:
        if x == '1':
            answer += 1
        else:
            continue
    return answer

재귀함수 특성상 시간이 오래 걸린다. 효율성에서 탈락.

1. 5자리 단위로 반복되는 규칙을 통한 문제풀이 (재귀 x)

기본적으로 solution 함수는 n 번째 유사 칸토어 비트열에서 l과 r 사이의 구간 내의 1의 개수를 계산하는 함수이다.

여기에서 나는 n 번째 유사 칸토어 비트열에서 k 번째 위치까지의 1의 개수를 계산하는 five 함수를 정의하였다.

five(n, r)이 n 번째 유사 칸토어 비트열에서 r 번째 위치까지의 1의 개수를 계산하고,

five(n, l-1)이 n 번째 유사 칸토어 비트열에서 l-1 번째 위치까지의 1의 개수를 계산하기 때문에 두 값을 빼면 l과 r 사이의 구간 내의 1의 개수가 되며

solution 함수는 five(n, r) - five(n, l-1)을 반환하게 된다.

설명 feat.Bing chat

def five(n, k):
    if n==1:
        if k <= 2:
            return k
        else:
            return k-1
        
    div = 5**(n-1)
    one = 4**(n-1)
    iloc = k//div
    
    if k%div==0:
        iloc -= 1
    
    if iloc < 2:
        return one*iloc + five(n-1, k-(iloc*div))
    elif iloc == 2:
        return one*iloc
    else:
        return one*(iloc-1) + five(n-1, k-(iloc*div))
    
solution = lambda n, l, r:five(n, r)-five(n, l-1)

오류나 틀린 부분이 있을 경우 언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다!

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기