[JS] 유사 칸코어 비트열

문제

프로그래머스

 

 

풀이

필자는 해당 문제를 단순 구현으로 풀이하려 했다. DP 알고리즘을 이용해 이전 문자열 + '0'.repeat(5 ** (i - 1)) + 이전 문자열 로 문자열을 구해 풀려했지만, 특정 케이스에서는 컴파일 에러가 발생했다.

 

그래서 수학적인 접근을 시도했다. 우선 문자열에서 규칙을 찾아보자면, 1의 개수는 4 * n개 이다. 그리고 0은 5개로 자른 문자열에서 항상 2번 인덱스에 위치한다.

 

이와같은 특징을 이용해 1과 0을 구분할 수 있는 check 함수를 제작해보자.

check 함수에서는 크게 3가지 경우를 처리한다.

1. 입력된 인덱스 값이 5보다 작으며, 5로 나눈 나머지가 2인지 아닌지

2. 인덱스 값이 5보다 크지만, (인덱스값 - 2) % 5 가 0인 경우는 5개 이후 연속되는 5개의 문자열에서 2번째 위치를 차지하는지 검증해야 한다.

3. 만약 위의 두 개의 조건에 부합하지 않는다면, 5로 나눈 몫을 재귀적으로 check 함수를 호출해야 한다.

 

코드

const solution = (n, l, r) => {
  let cnt = 0;
    
  const check = (index) => {
    if (index < 5) {
      return index % 5 === 2 ? false : true;
    }
    if ((index - 2) % 5 === 0) return false;
    return check(Math.floor(index / 5));
        
  }
    
  for (let i = l - 1; i < r; i++) {
    if (check(i)) {
      cnt += 1;
    }
  }
    
  return cnt;
};