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

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

프로그래머스

코딩테스트 연습 > 연습문제 > 유사 칸토어 비트열

 

난이도: LEVEL2

알고리즘 유형: 구현

문제 풀이

 n번째 유사 칸토어 비트열은 n-1번째 비트열에서 1은 11011로 치환  0은 00000 치환하여 만든다.

 

0 번째 유사 칸토어 비트열은 "1" 고정이다.

 

그럼 n번째 유사 칸토어 비트열 길이는 5^n이다. 

 

매번 1을 11011 0을 00000으로 치환해서 직접 유사 칸토어 비트열 문자열을 만들고 

주어진 index 범위를 서칭하는 건 시간 초과에 걸린다. 

 

그럼 어떻게 풀어야 할까? 

 

유사 칸토어 비트열에서 0이 나오는 자리는 규칙적이다. 

 

                                        1                                              → 1
       1               1              0             1               1              → 5
 1 1 0 1 1   1 1 0 1 1  0 0 0 0 0  1 1 0 1 1  1 1 0 1 1        → 25

 

유사 칸토어 비트열 0번째 ~ 2번째이다. 

1번째 유사 칸토어 비트열의 0인 index = 2

2번째 유사 칸토어 비트열의 0인 index = {2, 7, 10, 11, 12, 13, 14, 17, 22}

 

→ 해당 index를 5진법으로 변환했을 때 2가 존재하면 해당 index는 0이다. 

정답 코드 

class Solution {
    public int solution(int n, long l, long r) {
        int answer = 0;
        for(long i = l - 1; i <= r - 1; i++){
            boolean flag = true;
            long start = i;
            while(start >= 5){
                if(start % 5 == 2){
                    flag = false;
                    break;
                }
                start /= 5;
            }
            if(start == 2) flag = false;
            if(flag) answer++;
        }
        return answer;
    }
}