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

 

 

문제분석

나에겐 어렵다..  Level3? 3.5 정도 문제 아닌가..?

 

문제 이해부터 조금 난해한데,   요약하자면 1을 11011 ,  0을 00000으로 치환하여 n만큼 반복시킨다.

 

그렇게 반복시킨 문자열에서  스타트 l에서  끝지점 r까지 1의 갯수를 세주면 된다.

 

 

First Try: 

 

처음엔 그냥 쉽네 하고 하라는데로 진행을했다.

 

n만큼  1과 0을 치환한뒤,  그 문자열을 가져와서  스타트 l에서 끝지점 r까지 갯수를 세준것이다.

 

 

-> 당연히 효율성에러

 

Level2 에서 효율성 에러를 본게 참 오랜만이다. 

n이 20까지 가기때문에 5^20 까지간다.  int 범위를 넘어갈정도니, 당연히 안된다.

 

 

 

 

Secont Try:

**점화식, 재귀 작성하기 **

 

첫번째 접근이 안된다면,  값을 추적해야한다.

 

작전 :  0~ 끝 지점 - 0~ 스타트지점 구하기

 

규칙을 살펴보면,  1 하나가 11011을 생성한다. 즉 , n이 증가할때마다, 1은 1을 4개씩 생성이된다.

 

EX) n이 2번 진행되면,  문자열은 5^2개,  1의 숫자는 4^2개 생성된다.

 

하지만 , 숫자가 0일경우는 생성이 되지않는다.  이럴경우도 빼줘야한다.

 

 

이제부터, 값을 역추절 할것이다.   예를들어, 추적할 값이 17이라고 가정하자.

 

추적할 값이 17이면,  17은  25(5^2)보다 작은수다.  그렇다면 5^1로 나눠줍니다.

 

몫은 3,  나머지는 2가 나옵니다.

 

앞에서 1의 숫자가 4^n개만큼 생성이 됨을 알았으니,  총 1의갯수는 3* 4^1 입니다.

 

하지만 몫이 3이상이면, 다시 4^1개를 빼줘야합니다. 이유는 0이 끼어있기 때문입니다.    

 

그 후, 나머지를 다시 재귀를 해줍니다. 

 

전체풀이

import java.util.*;
class Solution {
    public int solution(int n, long l, long r) {
        int answer = 0;
 
        double a=getCount(r)-getCount(l-1);    
 
        answer=(int)a;
 
        return answer;
    }
 
    public long getCount(long num){
 
        int[] fk = new int[]{0,1,2,2,3,4};
 
        if(num<=5){
            return fk[(int)num];
        }
 
        int level=1;
 
        while(num>Math.pow(5,level+1)){
            level++;
        }
 
 
        long box = num/(long)(Math.pow(5,level));
        long remain = num%(long)(Math.pow(5,level));
 
        long count=box*(long)Math.pow(4,level);
 
        if(box>=3){
           count-=Math.pow(4,level);
        }
 
        if(box==2){
            return count;
        }
        else {
            return count+getCount((long)remain);
        }
    }
}

 

사실 혼자 힘으로 풀진 못한 문제다.

항상 이런 새로운 점화식을 찾아내, 재귀로 구현하는부분은 조금 약한것 같다. 

 

조금 더 길러야하는 생각이 많이 드는 문제다.