[Java] Lv.2 유사 칸토어 비트열

문제

 

프로그래머스

 

문제 풀이

비트열이 11011이라고 할 때 이때 각 자리수를 01234(1~5구역)로 두게되면 0의 위치는 n * 5  + 2(3구역)이다.

즉 자리수 i에 대해 i  % 5 == 2가 성립하게 되면 그 자리는 0이다.

다만 n이 무수히 증가 할 때 2번째 자리(3구역)에 위치한 0은 무수한 0의 5제곱 수 이다. 이 0들은 바로 % 5를 해버리면 어떤 값이 나오든 0인지 1인지 구할 수 없게 된다. 그래서 해당 자리 수의 몫( i / 5)을 구하면 그 0들의 이전 구간으로 축소된다. 

무슨 소리인고 하니 

n =2 인 1101111011000001101111011로 예를들면 중간의 10 ~ 14 자리 수 구간은 n이 늘어날 때마다 0이 5제곱씩 확장되는 구간이다. 이 때 해당 구간을 5로 무한히 나누어 몫을 구하게 되면 이전 n = 1일 때의 구간의 자리 수를 구할 수 있게 된단 소리이다. 

ex n =2 일때 11번째 자리수는 11 / 5 == 2   즉 11번째 자리수는 n=1 일 때 2번째 자리에 해당하는 수라는 것. 즉 0이다.

ex2 n = 3 일때 56번째 자리수는 56 / 5 == 11 즉 56번째 자리수는 n = 2 일 때 11번째 자리에 해당하는 수라는 것. 

한 번 더 몫을 구하게 되면 위의 처럼 다시 n = 1이 일 때 2번째 자리에 해당하는 수라는 것이 확인. 즉 0이다.

그렇게 몫만 챙기면서 5보다 작을 때 까지 나눴을 때 나머지가 2이면 0, 아니면 1이라고 하면 된다.

자바 코드

class Solution {
    public int solution(int n, long l, long r) {
        int answer = 0;
        // l-1부터 r까지의 범위를 체크
        for(long i = l-1; i < r; i++){
            if(!check(i)){
                continue;
            }
            
            answer++;
        }
        return answer;
    }
    public boolean check(long n){
        // 나머지가 2가 나오면 0
        if(n % 5 == 2)
            return false;
        // n이 2를 제외한 4이하면 1
        if(n < 5)
            return true;
        
        // n이 5보다 크면서 나머지가 2가 아닐 경우에는 몫을 구해서 재귀
        // 몫을 구하면 이전 구간을 확인할 수 있다.
        return check(n / 5);
    }
}