[프로그래머스] 유사 칸토어 배열 (Python)

Problem : 

Status :

Time :

 

---

 

문제 설명

 

수학에서 칸토어 집합은 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 ≤ 5^n
  • l ≤ r < l + 10,000,000
  • l과 r은 비트열에서의 인덱스(1-base)이며 폐구간 [l, r]을 나타냅니다.

 

입출력 예

n	l	r	result
2	4	17	8

 

 

---

 

풀이

이 문제를 풀면서 이전에 풀었던 문제(2022.12.29 - [알고리즘 문제/프로그래머스] - [프로그래머스] 단속카메라 (Python))가 생각나는 건 어쩔 수 없는 것 같다.

[프로그래머스] 단속카메라 (Python)

이 문제 역시 수학적 성질을 통해 해답을 찾아내가는 과정이며, 위 문제와의 차이라면 별다른 알고리즘을 요구하지 않는다는 점이다. 그래서 LV2로 책정된 게 아닌가 싶다. 지금 풀이 코드도 일일히 경우의 수를 적다 보니 그렇게 깔끔한 편은 아닌 점 유념바란다.

문제에서 주어진 유사 칸토어 수열은, 다음과 같은 성질들을 가지게 된다.

1. n번째 문자열을 S_(n)이라고 하면, S_(n)의 총 길이는 5^n, 그 중 1의 개수는 4^n이다.
2. 또한, S_(n)은 다음과 같이, S_(n) = S_(n-1) + S_(n-1) + "0"*(5^(n-1)) + S_(n-1) + S_(n-1) 를 만족하는 재귀적 형태로 표현 가능하다. 이는 1번 성질을 만족함을 알 수 있다.

 

S_(0) = 1, S_(1) = 11011이며, 재귀적으로 다음 성질을 만족함을 쉽게 알 수 있다. 여기서부터 시작하자.

우리는 S_(n) 에서의 [l, r] 범위 사이의 1의 개수를 알고 싶으므로, 다음과 같이 ([1, r] 범위 사이의 1의 개수) - ([1, l-1] 범위 사이의 1의 개수) 로 변환할 수 있다. 이런 식으로 문제를 처음부터 r번째까지의 1의 수열 개수를 탐색하는 문제로 치환할 수 있다. 2번 성질처럼 이 수열을 다섯 구간으로 나누고 본격적으로 풀이를 시작할 수 있겠다.

11011....

11011....

00000....

11011....

11011.....

 

모든 구간의 길이는 1번 성질에 따라 5^(n-1)의 길이로 이루어져 있으며, 3번 구간을 제외하고 4^(n-1)개의 1을 보유하고 있다. 또한 3번 구간을 제외하고 S_(n-1)과 동일하다. 즉 지금 구간까지의 1의 개수 + S_(n-1) 에서의 [1, r - 지금 구간의 길이] 내의 1의 개수를 구하면 우리가 구하고자 하는 1의 개수를 구할 수 있고, 이는 재귀적 문제에 해당한다.

 

 

풀이 코드

def solution(n, l, r):
    if n == 0 :
        return 1
    if l > 1 :
        return solution(n, 0, r) - solution(n, 0, l-1)
    if r <= 5 ** (n-1) :
        return solution(n-1, l, r)
    elif r <= 2 * 5 ** (n-1) :
        return 4 ** (n-1) + solution(n-1, l, r - 5 ** (n-1))
    elif r <= 3 * 5 ** (n-1) :
        return 4 ** (n-1) * 2
    elif r <= 4 * 5 ** (n-1) :
        return 4 ** (n-1) * 2 + solution(n-1, l, r - 5 ** (n-1) * 3)
    else :
        return 4 ** (n-1) * 3 + solution(n-1, l, r - 5 ** (n-1) * 4)
    
    return 4 ** n