[Javascript] 프로그래머스 - 유사 칸토어 비트열

문제 설명

유사 칸토어 비트열은 특정 규칙을 따라 생성되는 문자열입니다.

• 0번째 비트열은 "1"입니다.
• n번째 비트열은 이전 비트열에서 "1"을 "11011", "0"을 "00000"으로 치환하여 만듭니다.

이때, n번째 비트열에서 주어진 구간 [l, r] 내에 존재하는 "1"의 개수를 구하는 문제입니다.

---

제한 사항

• 1 ≤ n ≤ 20
• 1 ≤ l, r ≤ 5^n
• l ≤ r < l + 10,000,000

---

해결 방법

알고리즘: 분할 정복, 재귀

1. 유사 칸토어 비트열은 5개의 구간으로 나뉘며, 가운데(3번째) 구간은 항상 "0"으로만 구성됩니다.
2. 재귀적으로 n-1 비트열의 정보를 이용하여 l부터 r까지의 "1" 개수를 구합니다.
3. n번째 비트열에서 각 부분이 차지하는 범위를 계산하고,
   • 범위가 [l, r]과 겹치지 않으면 탐색하지 않음.
   • 완전히 포함되면 사전 계산된 "1" 개수를 더함.
   • 일부만 포함되면 더 작은 n-1 비트열로 범위를 좁혀 탐색.
4. 최종적으로 모든 범위에서 "1"의 개수를 합산하여 반환합니다.

---

시간 복잡도

• 5의 지수승 크기의 비트열을 직접 생성하는 것은 비효율적이므로 분할 정복을 활용하여 탐색 범위를 줄임.
• 최악의 경우에도 O(log r) 수준에서 해결할 수 있음.

---

구현 코드

function getOne(l, r, n, offset = 0) {
  if (n == 0) return 1;

  let size = 5 ** (n - 1);
  let count = 0;
  for (let i = 0; i < 5; i++) {
    let start = offset + i * size;
    let end = start + size - 1;

    if (end < l || start > r) continue;
    if (i === 2) continue;

    if (l <= start && end <= r) {
      count += 4 ** (n - 1);
    } else {
      count += getOne(l, r, n - 1, start);
    }
  }

  return count;
}

function solution(n, l, r) {
  return getOne(l - 1, r - 1, n);
}