유사 칸토어 비트열 - 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 함수를 완성해주세요.

풀이 과정

먼저 n번만큼 과정을 반복해 수열을 만들어주고 구간내에서 1의 개수를 찾아주면 된다고 생각했다.

class Solution {
fun solution(n: Int, l: Long, r: Long): Int {
    var current = "1"

    for (i in 1..n) {
        current = current.toList().joinToString("") { if (it == '1') "11011" else "00000" }
    }

    return current.substring(l.toInt() - 1, r.toInt()).count { it == '1' }
}

}

그러나 n이 최대 20이고 l,r이 Long타입인것을 감안했을때 다른 방법을 찾아야 했다.

1차 개선 (정확성, 효율성)

힌트풀이를 보고 힌트를 얻어 코드를 작성할 수 있었다..
n이 몇이 되건간에 동일한 index에는 값이 변하지 않기 때문에 n은 의미가 없었고, l과 r사이의 구간에 몇 개의 1이 존재하는지만 세면 된다.
마찬가지로 l과 r사이의 구간에도 규칙적으로 숫자가 존재하므로 재귀함수를 통해 검사함수를 만들 수 있었다.

fun solution(n: Int, l: Long, r: Long): Int {
    var answer = 0

    fun checkNumber(number: Long): Boolean {
        if (number < 5 && number != 2L) return true
        if ((number - 2) % 5 == 0L) return false
        return checkNumber(number / 5)
    }

    for (i in l - 1 until r) {
        if (checkNumber(i)) answer++
    }
    return answer
}

index이기 때문에 (l-1) 과 (r-1)사이의 구간에서 검사해주었다.
"11011"의 구조이므로 검사 숫자에서 2를 뺀 index가 5로 나누어진다면 가운데 "0"인 경우 이므로 false를 반환하게 해주었다.
그리고 첫 5까지의 index의 처리를 위해 첫 줄에 가운데 0을 제외한 나머지 숫자를 true반환 해 줄수 있었다.
둘 다 해당하지 않는 경우 숫자가 높은 상태이므로 5로 나누어 다시 구간 처리를 해줄 수 있었다.