[JAVA] Pro 유사 칸토어 비트열

문제

https://school.programmers.co.kr/learn/courses/30/lessons/148652?language=java# 

프로그래머스

코드

class Solution {
    // 1~k번째 까지 1이 몇개 존재하는지
    public long cal(int n, long k){
        long temp=0;
        long pre=0;
        for(int i=n; i>=0; i--){
            long t=k/(long)Math.pow(5,i);
            k-=t*(long)Math.pow(5,i);
            
            if(pre==2) continue;
            pre=t;
            
            if(t>=3) t--;
            temp+=t*((long)Math.pow(4,i));
        }
        return temp;
    }
    
    
    public long solution(int n, long l, long r) {
        // [left,right] -> [1,right] - [1,left-1]
        return cal(n,r)-cal(n,l-1);
    }
}

풀이

1. [left,right] -> [1,right] - [1,left-1]

2. 1~K까지 1의 개수를 구할 때 5^n패턴을 이용

27을 5^n패턴으로 분해하면 5^2이 1개 5^0이 2개이다

각 패턴은 1을 4^n만큼 가지고 있으므로 4^2+2 =18이다.

 

38을 5^n패턴으로 분해하면 5^2이 1개 5^1이 2개 5^0이 3개이다.

각 패턴은 1을 4^n만큼 가지고 있으므로 4^2+4*2+3이여야 되나 바로 직전 패턴의 개수가 2개이면 문제 규칙상 다음 패턴은 다 0이므로 예외처리를 해준다.

 

어려웠던 부분

재귀를 이용해 해결하려 했으나 머리가 터질거 같아서 다른 사람의 풀이를 참고하였다.

 

 

class Solution {
    public int solution(int n, long l, long r) {
        // n은 사실상 무의미,,
        int answer = 0;
        long start = l-1;
        long end = r;
        for (long now = start; now < end; now++) {
            // 1인 경우에만 더해주기
            answer += getNumber(now);
        }
        return answer;
    }

    int getNumber(long now) {
        // 범위를 0~4인 경우
        if (now < 5) {
            if (now == 2) {
                return 0;
            }
            return 1;
        }

        // 확실한 0: 아예 5의 배수로 영역 분할 했을 때, 중간값인 경우 항상 0
        if (now % 5 == 2) {
            return 0;
        } else {
            // 부모를 찾아봐야하는 경우 -> 중간값은 아니지만, 부모가 0일 수 있음 -> 부모가 0일때까지 재귀적으로 탐색, 1일 경우는 0~4 범위에서 부모가 1인것으로 판단하여 종료!
            return getNumber(now / 5);
        }
    }
}