[JS] 유사 칸토어 비트열

생각보다 너무 까다로운 문제였다...

 

처음에 문제를 딱 보았을때는 수학적 성질을 활용해서 간단하게 풀거나, 재귀함수로 풀 수 있겠다라는 생각이 들었다.

 

 

수학적 성질을 활용해서 풀어보려고 머리를 쓰다가 포기하고 결국은 재귀함수를 활용해서 풀기로 해보았다.

결국 두 좌표의 차이를 계산하기 위해서는 r까지의 1의 개수,  l까지의 1의 개수를 구한 다음, 두 수의 차를 구하면 되는 문제이다.

 

 

처음에 굉장히 많이 헤맸는데, 해당 배열을 재귀로 넘겨줄때 5로 나누어진 몫을 넘겨줘야 한다고 생각했었다.

 

 

11011 11011 00000 11011 11 까지 만약에 다음 재귀사이클로 넘겨준다면 ,

 

11011 11011 00000 11011 즉 4라는 값을 넘겨주고, 11을 1의개수를세면 된다고 생각했었다.

 

 

그런데 전혀 반대로 생각하고 있었다..

 

몫 부분은 5의 n제곱 *4라는 값으로 1의 개수를 쉽게 셀 수 있었고 오히려 나머지 부분을 세는 것이 문제였다.

 

 

 

 

아래 방법이 가능한 이유는, 결국 n+1 로 만드는 값을 n의 온전한 숫자 하나로 만들기 위해서는 n**5개의 값이 필요하기 때문이다.

 

 

function solution(n, l, r) {
    const oneCnt = [0,1,2,2,3,4]
    
    const recur = (n,pos) => {
        
        if (n==1) return oneCnt[pos]
        const [share,remain] = [~~(pos/(5 ** (n-1))),pos%(5 ** (n-1))]
        
        if (share<2) return 4**(n-1) * share + recur(n-1,remain) 
        else if (share === 2) return 2 * 4**(n-1)
        else return 4**(n-1) * (share-1) + recur(n-1,remain)
        
    }
    return recur(n,r) - recur(n,l-1)
}