프로그래머스 Lv.2(JS) - 유사 칸토어 비트열

문제

---

정답

풀이 코드

function solution(n, l, r) {
  const calcBit = (index) => {
    let exp = 0;
    let result = 0;

    while (index > 5 ** (exp + 1)) exp++;
    if (exp === 0) return index < 3 ? index : index - 1;

    const quotient = Math.floor(index / 5 ** exp);
    const remainder = quotient + 1 !== 3 ? index % 5 ** exp : 0;

    result += quotient >= 3 ? (quotient - 1) * 4 ** exp : quotient * 4 ** exp;

    return result + calcBit(remainder);
  };

  return calcBit(r) - calcBit(l - 1);
}

풀이 설명

const calcBit = (index) => {
  let exp = 0;
  let result = 0;

  while (index > 5 ** (exp + 1)) exp++;
  if (exp === 0) return index < 3 ? index : index - 1;
};

calcBit는 0번 인덱스부터 주어진 index까지의 구간에서 1의 개수를 반환하는 재귀 함수입니다.

• 먼저 index보다 작거나 같은 5ⁿ 중 가장 큰 n(=exp)값을 구합니다.
  예를 들어 index가 17이라면 exp는 1입니다.(5¹ < 17 < 5²)

index가 5 미만일 경우(exp===0)에는 전체 비트열이 11011이므로 아래와 같은 방법으로 처리합니다.

• index < 3 → 1의 개수는 index와 같습니다.
• index >= 3 → 3번째는 항상 0이므로 1의 개수는 index-1

const calcBit = (index) => {
  //...
  const quotient = Math.floor(index / 5 ** exp);
  const remainder = quotient + 1 !== 3 ? index % 5 ** exp : 0;

  result += quotient >= 3 ? (quotient - 1) * 4 ** exp : quotient * 4 ** exp;

  return result + calcBit(remainder);
};

quotient는 구간이 5개로 나뉘었을 때 index가 몇 번째 구간에 속하는지 나타냅니다.

remainder는 아래 두 가지 경우로 나눌 수 있습니다.

• quotient가 2인 경우: 나머지는 항상 0이 되는 중앙 구간이므로 이후 탐색을 막기 위해 0을 저장합니다.

• 그 외의 경우: index를 5^exp로 나눈 나머지를 저장합니다.

quotient가 3 이상인 경우, 중앙 구간(3번째)을 포함하므로 quotient - 1에 4^exp를 곱합니다. 3 미만의 경우에는 단순히 quotient*4exp만큼 1이 존재합니다.

해당 값을 result에 누적하고 나머지 구간에 대해서는 calcBit를 재귀 호출합니다.

function solution(n, l, r) {
  const calcBit = (index) => {
    //...
  };

  return calcBit(r) - calcBit(l - 1);
}

폐구간 [l, r]은 l과 r의 인덱스를 모두 포함하므로 0부터 r까지의 1의 개수에서 0부터 l-1까지의 1의 개수를 뺀 결과를 리턴합니다.

---

References

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