유사 칸토어 비트열(프로그래머스-연습문제)

문제

코드

class Solution {
    public int solution(int n, long l, long r) {   
        long[] arr=new long[20];
        long a=1;
        for(int i=0;i<20;i++){
            arr[i]=a;
            a*=4;
        }
        return (int)(sum(r,n,arr)-sum(l-1,n,arr));
    }
    public long sum(long num,int n,long[] arr){
        long result=0;
        long quotient=num/(long)Math.pow(5,n-1);
        long remainder=num%(long)Math.pow(5,n-1);
        while(true){
            for(int i=1;i<=quotient;i++){
                if(i==3) continue;
                result+=arr[n-1];
            }
            if(quotient!=2&&n>1){
                if(remainder<=5){
                    for(int i=1;i<=remainder;i++){
                        if(i==3) continue;
                        result+=1;
                    }
                    break;
                }
                else{
                    quotient=remainder/(long)Math.pow(5,n-2);
                    remainder=remainder%(long)Math.pow(5,n-2);
                    n--;                    
                }
            }
            else break;
        }
        return result;
    }
}

풀이

이 유사 칸토어 비트열의 전체적인 구조에 대해 파악해야 한다.
글로 설명하기가 좀 힘든 내용이다.
"ㅁ"이 하나의 "11011" 또는 "00000"이라고 하자.
먼저, n이 1일때는 "11011" 이다.
n이 2일때는 "ㅁㅁㅁㅁㅁ"이다.
n이 3일때는 "ㅁㅁㅁㅁㅁ ㅁㅁㅁㅁㅁ ㅁㅁㅁㅁㅁ ㅁㅁㅁㅁㅁ ㅁㅁㅁㅁㅁ"이다.
n이 늘어날 수록 크기는 5배씩 커지고, 하나의 "ㅁ"이 다섯개의 "ㅁ"을 만든다. 그리고, 전체의 중앙부분이나, "ㅁㅁㅁㅁㅁ"의 가운데 "ㅁ"은 모두 "0"으로만 구성되어 있다.

나는 r까지 센 1의 개수에서 l-1 까지 센 1의 개수를 빼는 방식으로 했다.
num까지의 1의 개수를 구하는 법은 다음과 같다.
핵심은 전체에서 num의 위치를 찾는 것이다.
(1) num을 5^n-1 로 나눈 몫과 나머지를 구한다.(만약 n이 3이라면, 전체 크기는 25개의 세트가 5개 있는 125이다. 그렇게 때문에 25로 나누어 준 것이다.)
(2) 몫이 전체를 5개로 나누었을때의 위치이다. 일단 큰 것부터 먼저 계산해 준다. 가운데 부분을 제외하고 answer(1의 개수)+=arr[n-1]을 해준다. (arr은 n의 크기에 따라 한 세트에 들어있는 1의 개수를 미리 저장해 둔 배열이다.)
(3) 나머지가 5보다 크다면, 나머지를 5^n-2 나눈 것이 몫이 되고, 그 나머지가 다시 나머지가 된다. n-- 를 해주고, 다시 while문으로 들어간다.(이제 나머지가 속한 부분을 다시 분할해주어야 한다.)
(4) 나머지를 계속 분할해서 위치를 찾아 쪼개면서 answer을 늘려준다.

• 몫이 2이거나,n이 1보다 작은 경우는 나머지를 계산하지 않는다.(몫이 2면, 나머지는 무조건 모든 부분이 0인 세트에 존재하기 때문이다.)
• 나머지가 5 이하가 되면, 그냥 "11011" 부분을 계산하면 되기 때문에 가운데 부분을 제외하고 1의 개수만 더해주고 while문을 종료한다.

결과

시간이 정말 너무 많이 걸렸던 문제이다.
제한 조건을 보니 1의 개수를 직접 구하는 것은 절대 아니라고 판단했고, 무조건 규칙을 찾아 수식을 세우는 문제라고 생각했다.
접근은 잘 한 것 같은데, 규칙을 잘 찾지 못했다.
똑같은 부분이 5세트씩 계속 더 만들어지는 것을 이용해서 반복문을 돌려야 하는데, 너무 어거지로 풀려고만 했다.
시간을 너무 많이 썼다 보니까, 코드를 더 깔끔하게 고칠 수 있을 것 같은데 일단 스트레스 받아서 저대로 뒀다.
그래도 좀 어려웠는데 풀어서 뿌듯하긴 하다.
출처 : 프로그래머스 코딩 테스트 연습 https://school.programmers.co.kr/learn/challenges