문제

풀이 과정

요약

슬라이딩 윈도우를 통해 탐색하였다. 단 범위가 어느정도 있으므로, 시간초과가 나올 수 있기 떄문에, 백트래킹을 넣었다.

상세

슬라이딩 윈도우를 통해 5구간 씩 나누어 살펴볼것이다. 재귀를 만드는데 나의 경우에는 depth, 구간의 시작점, 구간의 끝점, 현재구간에 들어가야하는 문자를 매개변수로 넣었다.

사용한 백트래킹 요소들은 다음과 같다.

• 수학적으로 접근하자면, $N$ 번째 유사 칸토어 비트열의 총 수는 $5^N$ 이라는 것을 알 수 있다.
  0번째 : $5^0 = "1" => 1개$
  1번째 : $5^1 = "11011" => 5개$
  2번째 : $5^2 = "1101111011000001101111011" => 25개$
  ...
  $N$번째 : $5^N$개

• 따라서, 현재의 $d$ 번째 유사 칸토어 비트열의 인덱스가 $N$ 번째 유사 칸토어 비트열의 $l$, $r$의 범위에 도달하는지 확인할 수 있다. $d$번째 유사 칸토어 비트열의 인덱스를 $i$라고 한다면 해당 식은 다음과 같다.

  $5^{N-d}*i$

• 예를들어, 1번째 유사 칸토어 비트열 “11011” 가운데, 1번째 “1” 의 인덱스는 0이며, 해당 수는 2번째 유사 칸토어 비트열에서는 인덱스 0 에서 4번째 까지, 3번째 유사 칸토어 비트열의 에서는 0 에서 24 번째까지 영향을 미치게 된다.

• 따라서, 해당 식을 통해 영향을 미치는 인덱스만 depth 를 올려 더 탐색해서 시간을 줄일 수 있었다. 또또한 0 을 “00000” 으로 바꿔야 하는데, 문제는 1의 갯수만 구하면 되는 문제이므로, 이 부분도 거르고 재귀를 돌리는 게 더 빠르다.

• $N$ 번째 까지 도달한 경우, 나타날 수 있는 $l$ , $r$ 경우의 수는 총 4가지 이다. 현재 슬라이딩 윈도우의 좌표를 $currL$, $currR$ 이라고 한다면

  • $currL$ , $currR$ 모두 $l$ 보다는 크거나 같거나 $r$ 보다 작거나 같은 경우
    • $ans$에 4를 더해준다. (”0” 부분은 재귀에 반영되지 않는다. $N$번째에 도달하는 모든 문자는 “11011” 로 해당 범위에 반영되는 경우 항상 “1” 은 4개이다. )
  • $currL$ 은 $l$ 보다 작지만, $currR$ 은 $l$ 과 $r$ 사이에 들어오는 경우
    • $l$ 부터 $currR$ 까지만 탐색한다.
  • $currR$ 이 $r$ 보다 크지만 $currL$ 은 $l$ 과 $r$ 사이에 들어오는 경우
    • $currL$ 부터 $r$ 까지만 탐색한다.
  • 첫번째 경우와 동일하나, 해당 $l$, $r$ 의 범위가 5보다 작은 경우

    ex. 2번째 유사 칸토어 비트열에서 12~14 사이의 1의 갯수를 찾는 경우.

    • $l$ 부터 $r$ 까지 탐색한다.

정답

let ans = 0;
let N,L,R;
function solution(n, l, r) {
    [N,L,R] = [n,l-1,r-1]; 
    recur(1,0,4,"11011");
    return ans;
}

function recur(d, currL, currR, val) {
    if(d>=N) {
        if(L<=currL && currL <= R && L<=currR && currR<=R) ans += val[0] == "1" ? 4 : 0;
        else if(currL<L && L<=currR && currR<=R) for(let i=L%5; i<=currR%5; i++) val[i]=="1" && ans++; 
        else if(L<=currL && currL <= R && currR>R) for(let i=currL%5; i<=R%5; i++) val[i]=="1" && ans++; 
        else if(currL<=L && R<=currR) for(let i=L%5; i<=R%5; i++) val[i]=="1" && ans++;
        return;
    } 
        
    for(let i=currL; i<=currR; i++) {
        let tempL = Math.pow(5,N-d)*i;
        let tempR = tempL + Math.pow(5,N-d)-1;
        if((tempL <L && tempR <L) || (tempL >R && tempR >R)) continue;
        val[i%5]=="1" && recur(d+1, i*5, i*5+4, "11011");
    }
}