Level 2 ) 유사 칸토어 비트열 ⭐️

문제 설명

수학에서 칸토어 집합은 0과 1 사이의 실수로 이루어진 집합으로, [0, 1]부터 시작하여 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만들어집니다.

남아는 칸토어 집합을 조금 변형하여 유사 칸토어 비트열을 만들었습니다. 유사 칸토어 비트열은 다음과 같이 정의됩니다.

0 번째 유사 칸토어 비트열은 "1" 입니다.
n(1 ≤ n) 번째 유사 칸토어 비트열은 n - 1 번째 유사 칸토어 비트열에서의 1을 11011로 치환하고 0을 00000로 치환하여 만듭니다.
남아는 n 번째 유사 칸토어 비트열에서 특정 구간 내의 1의 개수가 몇 개인지 궁금해졌습니다.
n과 1의 개수가 몇 개인지 알고 싶은 구간을 나타내는 l, r이 주어졌을 때 그 구간 내의 1의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

1 ≤ n ≤ 20
1 ≤ l, r ≤ 5n
l ≤ r < l + 10,000,000
l과 r은 비트열에서의 인덱스(1-base)이며 폐구간 [l, r]을 나타냅니다.

입출력 예

n	l	r	result
2	4	17	8

입출력 예 설명

2 번째 유사 칸토어 비트열은 "1101111011000001101111011" 입니다. 음영 표시된 부분은 폐구간 [4, 17] 이며 구간 내의 1은 8개 있습니다.

풀이

시간 초과 발생

function solution(n, l, r) {
    let fir = "1";
    let count = 0;
    while(count < n){
        let arr = fir.split('');
        let next = arr.map(el => el === "1" ? "11011" : "00000").join('');
        count++;
        fir = next;
    }
    let answer = fir.slice(l-1,r);
    return answer.split('').filter(el => el === "1").length
}

신박한 풀이

해당 범위 부분만 5진수로 바꾸고 2를 포함하지 않는 경우(0이 아닌 경우)를 카운트 해주면 1의 개수를 구할 수 있다.

function solution(n, l, r) {
    let answer = 0;
    for (let i = l - 1; i <=r - 1; i++) {
        if (!i.toString(5).match('2')) answer += 1;
    }
    return answer;
}

규칙을 활용한 풀이

function solution(n, l, r) {
  let result = 0;
  let memo = new Array(r - l + 1).fill().map((_, idx) => idx + l);

  if (n === 1) {
      return memo.filter(el => el !== 3).length;
  }

  while(memo.length) {
    const newMemo = [];

    for (const el of memo) {
      if (el === 1) result += 1;
      else {
        if (!!((el + 2) % 5)) {
          const fixedEl = Math.ceil(el / 5);   
          newMemo.push(fixedEl);
        }
      }
    }

    memo = newMemo;
  }

  return result;    
}

https://dev-gp.tistory.com/163