[프로그래머스] Lv.2 유사 칸토어 비트열 (자바)

프로그래머스

 

문제 설명

유사 칸토어 비트열은 다음과 같이 정의됩니다.

•  0번째 유사 칸토어 비트열은 "1"입니다.
• n(1≤n) 번째 유사 칸토어 비트열은 n-1번째 비트열에서의 1을 11011로 치환하고 0을 00000으로 치환하여 만듭니다.

남아는 n번째 유사 칸토어 비트열에서 특정 구간 내의 1의 개수가 몇 개인지 궁금해졌습니다.

n과 1의 개수가 몇 개인지 알고 싶은 구간을 나타내는 l, r이 주어졌을 때 그 구간 내의 1의 개수를 return 하도록 solution 함수를 완성해 주세요.

---

문제 이해

n번째	유사 칸토어 비트열
0	1
1	11011
2	1101111011000001101111011

이런 식으로 n-1번째의 숫자를 0->00000, 1->11011로 치환하므로, n번째 유사 칸토어 비트열은 5^n길이를 가집니다.

---

풀이 과정

이 알고리즘은 큰 문제를 작게 쪼개서 해결할 수 있는 풀이로 DP(Dynamic Programming)의 방식으로 풀이를 진행합니다.

 

일단 큰 문제는 폐구간 [l, r]이 0과 1 중에 어떤 비트를 가지는지를 알아야 하는 것입니다.

이 문제를 작게 쪼개 보겠습니다.

 

 

n=1일 때 2번째 자리는 0이 나오고, 나머지 자리에는 모두 1이 들어가게 됩니다.

 

 

 

n=2 일 때도, 5개씩 잘랐을 때 2번째 자리에는 무조건 0이 나오는 것을 확인할 수 있습니다.

또한, 전체를 5개씩 자른 묶음 중에서도 2번째 묶음에는 모두 0이 나오는 것도 확인할 수 있습니다.

 

 

 

따라서, 이 문제의 규칙을 정리하면

1. 5개씩 잘랐을 때 자신의 위치가 그 안에서 2번째 이면 0이다.

2. 5개씩 잘랐을 때 묶음에 한에서도 2번째 묶음이라면 모두 0이다.

 

 

이 규칙을 코드에 적용한 전체 코드에 적용해 주석처리 하였습니다.

---

전체 코드

class Solution {
    public int solution(int n, long l, long r) {
        int answer = 0;
        
        for(long i=l-1;i<r;i++){
            answer+=findNum(i); //i번째 자리의 숫자를 answer에 더해줍니다.
        }
        return answer;
    }
    // x번째 비트가 0인지 1인지 반환.
    int findNum(long x){
        // 5개씩 잘랐을 때 그 묶음 안에서 2번째인 경우는 항상 0.
        if(x%5==2) return 0; 
        if(x==0) return 1; //끝까지 확인했는데 2번째인 적이 단 한번도 없다면 해당 비트는 1입니다.
        
        // 묶음으로 처리했을 때 x가 몇 번째 묶음에 속하는지 확인 
        //  -> 2. 그 묶음이 2번째 묶음이면 0.
        return findNum(x/5); 
    }
}