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

https://school.programmers.co.kr/learn/courses/30/lessons/148652

시나리오

1. n이 아무리 커져도 1 1 0 1 1 꼴은 반복된다. 

n=1 11011
n=2 11011 11011 00000 11011 11011
n=3 11011 11011 00000 11011 11011 11011 11011 00000 11011 11011 00000 00000 00000 00000 00000 11011 11011 00000 11011 11011  11011 11011 00000 11011 11011 
...

2. 위 규칙에 따라 비트열을 다섯등분 하고 등분한 덩어리를 또 다시 다섯등분하는 과정을 반복하는 재귀함수를 만든다.

3. 단, n이 몇이든 중간 덩어리는 무조건 0이므로 연산에서 제외하며, l과 r사이에 하나라도 포함되지 않는 덩어리 역시 제외한다.

4. 더 이상 쪼갤 수 없을 때 현재 요소가 1이라면 return 1을 해준다.

 

정답 코드

class Solution {
    public int solution(int n, long l, long r) {
        return recurse(n, l, r, 1);
    }
    
    private int recurse(int n, long l, long r, long criteria){
        if(n==0){
            return 1;
        }
        
        int currentCnt=0;
        //현재 n에서의 한 덩어리의 크기 는 5^n-1 즉, 5등분한 값이다.
        long part = (long)Math.pow(5.0,(double)n-1);
        
        for(int i=0; i<5; i++){
            //가운데 덩어리는 0이므로 continue. 현재 덩어리의 끝값이 l보다 작거나, 현재 덩어리의 시작값이 r보다 커도 continue 
            if(i==2||l>criteria+part*(i+1)-1||r<criteria+part*i){
                continue;
            }
            currentCnt += recurse(n-1, l, r, criteria+part*i);
        }
        return currentCnt;
    }
}

 

 

레퍼런스: https://velog.io/@ujone/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%9C%A0%EC%82%AC-%EC%B9%B8%ED%86%A0%EC%96%B4-%EB%B9%84%ED%8A%B8%EC%97%B4-JAVA

velog

 

새로 알게된 점

레퍼런스를 참고해서 혼자 풀던 특정 케이스에서만 오답이 나오는 상황이 발생했다. 틀린 점을 찾지 못해 레퍼런스 코드를 봤고 Math.pow의 리턴값을 (int)로 변환해서 풀었던 게 오답 원인이라는 것을 알게됐다.

n값이 20에 가까워지면 5^n의 값은 int의 범위를 넘어가기 때문에 long으로 담지 않으면 올바른 계산값이 나올 수 없던 것이다.

int범위를 넘어서는 입력이 주어지면 숫자 데이터 타입도 각별히 신경쓰자