문제
수학에서 칸토어 집합은 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,000l
과r
은 비트열에서의 인덱스(1-base)이며 폐구간 [l, r]을 나타냅니다.
입출력 예
입력
- n: 2
- l: 4
- r: 17
출력: 8
풀이
규칙 찾기
정의에 따르면
- 0번째 유사 칸토어 비트열 = 1
- n(1 ≤ n)번째 유사 칸토어 비트열 = n-1번째 유사 칸토어 비트열을 치환한 값
으로, 1번째 유사 칸토어 비트열은 0번째 유사 칸토어 비트열 1을 치환한 11011이 된다.
좀 더 살펴보면 2, 3번째 유사 칸토어 비트열은 아래와 같다
- 2번째 유사 칸토어 비트열 = 1번째 유사 칸토어 비트열(11011)을 치환한 값 = 11011 11011 00000 11011 11011
여기서 우리는 세 가지 규칙을 알 수 있다.
- n번째 유사 칸토어 비트열을 f(n)이라고 하면, f(1) = 11011이다. 즉,
f(n) = f(n-1) f(n-1) 0 f(n-1) f(n-1)
이 된다. - n번째 비트열은 5등분할 수 있다. 즉, f(n)에서 유사 칸토어 비트열 자릿수는
5^n
이다. (5진법) - f(n)에서 1은
4^n
개이다. (4진법)
시간 복잡도 고려하기
위에서 찾아낸 규칙에 따르면 유사 칸토어 비트열 자리수는 최대 5^20으로 자릿수가 13이나 된다.
여기에 r이 l + 10,000,000보다 작을 때 r - l < 10,000,000이므로 폐구간 [l, r]을 탐색하려면 그 길이가 최대 10^7이 된다.
그러므로 시간 복잡도 O(N)을 넘으면 안 된다.
분할 정복
비트열이 일정한 규칙을 가지며 다섯 등분할 수 있다는 점을 이용한다.
n=2
, l=17
, r=25
인 경우
- 2번째 비트열을 기준으로 17번째 비트부터 25번째 비트까지 1의 개수 = 25번째 비트까지 1의 개수 - 16번째 비트까지 1의 개수
- 2번째 비트열을 5개 구역(0,1,2,3,4)으로 나누면 17번째 비트는 구역 3, 25번째 비트는 구역 4에 위치한다.
2번째 비트열 25번째 비트까지 1의 개수 = 구역 3까지 1의 개수 + 구역 4에서 25번째까지 비트 수
- 구역 3까지 1의 개수 = 1번째 비트열 3개에 대한 1의 개수 = 4^1 * 3 = 12
- 구역 4에서 25번째까지 비트 수 = 1번째 비트열에서 5(25-5*4)번째 비트까지 1의 개수
16번째 비트까지 1의 개수 = 구역 2까지 1의 개수 + 구역 3에서 16번째까지 비트 수
- 구역 2까지 1의 개수 = 1번째 비트열 2개에 대한 1의 개수 = 4^1 * 2 = 8
- 구역 3에서 16번째까지 비트 수 = 1번째 비트열 1(16-5*3)번째 비트까지 1의 개수
n번째 비트열에서 k번째 비트까지 1의 개수를 구하는 함수 count(n, k)를 구현한다면 다음과 같이 표현할 수 있다.
count(n, k) = k구역 전까지 1의 개수 + count(n-1, k-(k구역 전까지 비트수))
zone = k구역(0~4)
count(n, k) =
if (zone == 2) 4^(n-1) * zone
if (zone > 2) 4^(n-1) * (zone-1) + count(n-1, k - (5^(n-1) * zone))
else 4^(n-1) * zone + count(n-1, k - (5^(n-1) * zone))
코드
import kotlin.math.abs
import kotlin.math.pow
class Solution {
fun solution(n: Int, l: Long, r: Long): Int {
return count(n, r) - count(n, l - 1)
}
private fun count(n: Int, k: Long): Int {
if (n == 0) return 1
val prevBitStringNumber = n - 1
val divisor = 5.0.pow(prevBitStringNumber).toLong() // 5등분으로 나누는 수
val numberOf1s = 4.0.pow(prevBitStringNumber).toInt() // 이전 비트열 1의 개수
var zone = abs(k / divisor).toInt() // k번째가 속한 구역(0, 1, 2, 3, 4)
if (k % divisor == 0L) zone -= 1
// 0만 있는 구역
if (zone == 2) return numberOf1s * zone
// 0 이후 구역
if (zone > 2) return numberOf1s * (zone - 1) + count(n - 1, k - (divisor * zone))
// 0 이전 구역
return numberOf1s * zone + count(n - 1, k - (divisor * zone))
}
}
테스트 1 〉 통과 (0.04ms, 62.1MB)
테스트 2 〉 통과 (0.04ms, 62.9MB)
테스트 3 〉 통과 (0.04ms, 62.2MB)
테스트 4 〉 통과 (0.06ms, 62.1MB)
테스트 5 〉 통과 (0.06ms, 59MB)
테스트 6 〉 통과 (0.04ms, 61.3MB)
테스트 7 〉 통과 (0.04ms, 60.8MB)
테스트 8 〉 통과 (0.04ms, 62.4MB)
테스트 9 〉 통과 (0.04ms, 62.5MB)
테스트 10 〉 통과 (0.04ms, 62.7MB)
테스트 11 〉 통과 (0.04ms, 62.4MB)
테스트 12 〉 통과 (0.04ms, 61.4MB)
테스트 13 〉 통과 (0.04ms, 62.1MB)
테스트 14 〉 통과 (0.04ms, 60.7MB)
테스트 15 〉 통과 (0.04ms, 59MB)