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

문제

링크

수학에서 칸토어 집합은 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: 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

여기서 우리는 세 가지 규칙을 알 수 있다.

1. n번째 유사 칸토어 비트열을 f(n)이라고 하면, f(1) = 11011이다. 즉, f(n) = f(n-1) f(n-1) 0 f(n-1) f(n-1)이 된다.
2. n번째 비트열은 5등분할 수 있다. 즉, f(n)에서 유사 칸토어 비트열 자릿수는 5^n이다. (5진법)
3. 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)