[Programmers] [Kotlin] 유사 칸토어 비트열

난이도 : Level 2 

 

푼 방법 : 분할 정복(?)

 

아이디어

1. 11011이 반복되는 형태이므로, 5^n의 비트열을 5단으로 쪼갠다.
2. 현재 탐색해야할 지점을 x로 한다면, 5^n에서 x의 위치를 단으로 나타낸다.
3. 문단 0,1,2,3,4 기준으로 2는 항상 0이 그려져 있으므로 2에 위치해 있다면 0
4. 2가 아닌 다른 위치라면 이 탐색 과정을 반복하면 11011로 도달.
5. 만약 11011에서도 1에 위치해 있다면 탐색 종료.

 

코드 구현

class Solution {
    fun solution(n: Int, l: Long, r: Long): Int {
        var answer: Int = 0
        var num = Math.pow(5.toDouble(),(n-1).toDouble()).toLong()
        answer = ((r-l)+1).toInt()
        for ( i in (l-1)..(r-1)) {
            var div = num
            var start = i
            while(div != 0L) {
                if ( start / div == 2L) {
                    answer--
                    break
                }
                start = start % div
                div /= 5L
            }
        }
        return answer
    }
}