[Programmers] 유사 칸토어 비트열 - JavaScript

Joosi_Cool·2023년 5월 15일
1

Programmers

목록 보기
95/98
post-thumbnail

문제설명



설계 과정

이번 문제는 코딩보다는 수학적 규칙을 찾는 것이 중요하다.
한번 예시를 봐보자.
n = 1 => 11011
n = 2 => 1101111011000001101111011
=> 4 4 0 4 4
n = 3 => 16 16 0 16 16
이런식으로 정리를 해보면
0인지 1인지 궁금한 index를 5로 나누었을때 나머지가 2가 나오는 경우는 중간에 위치함 -> 이는 0에 해당된다.
이를 제외하고는 1에 해당한다. -> 단, 1 같은 경우는 나머지가 2가 나오더라도 나눈 인덱스가 5 아래여야 한다.
=> 이유: 예를 들어 n=3에서 나눈 수가 1이 나와 16에 해당하더라도 16안에 0이 있는 경우도 있음. 따라서 n이 5보다 크다면 계속 5로 나눠서 5아래로 떨어뜨려야한다.

  • 이 과정을 코드로 만들면 아래와 같다.


정답 코드

function check(num){
    // 5이하로 떨어졌을때 11011이기 => 2만 제외하고 true리턴
  if (num < 5 && num != 2) return true;
    // 5개 중에 2번째 값은 0이기 때문에 false리턴
  if ((num - 2) % 5 === 0) return false;

    //만약 5를 넘고, 2번째 값이 아니라면 5를 나눠서 진행
  return check(Math.floor(num / 5));
}


function solution(n, l, r) {
    var answer = 0;
    for(var i = l-1; i<r;i++){
      if(check(i)){
        answer++;
      }
    }
    return answer;
}


결과

이런 문제는 코드 구현보다는 문제의 규칙을 찾아내는 것이 어렵다고 본다. 코드 구현은 빠르게 되었지만, 그 코드의 설계 자체가 매우 어려운 문제였다고 생각한다.



profile
집돌이 FE개발자의 노트

0개의 댓글