이번 문제는 코딩보다는 수학적 규칙을 찾는 것이 중요하다.
한번 예시를 봐보자.
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;
}
이런 문제는 코드 구현보다는 문제의 규칙을 찾아내는 것이 어렵다고 본다. 코드 구현은 빠르게 되었지만, 그 코드의 설계 자체가 매우 어려운 문제였다고 생각한다.