프로그래머스 - 유사 칸토어 비트열 (JavaScript)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/148652

프로그래머스

 

생각해보기

n = 1인 유사 칸토어 비트열을 만들기 위한 연산 횟수 : 1번

n = 2인 유사 칸토어 비트열을 만들기 위한 연산 횟수 : 1 + 5^1번

n = 3인 유사 칸토어 비트열을 만들기 위한 연산 횟수 : 1 + 5^1번 + 5^2번

 

n번째 유사 칸토어 비트열을 만들기 위해서는 1 + 5^1 + ... + 5^(n - 1)번의 연산이 필요하다. 또한, 해당 비트열 안에서 1의 개수를 탐색할 때 최대 비트열의 길이(5^n)만큼 연산을 수행한다.

 

변환의 시간 복잡도 : O(5^n)

탐색의 시간 복잡도 : O(5^n)

 

n은 최대 20이므로 시간 초과가 날 것이다. 또한, 위 방법대로 풀면 메모리 사용량 초과가 발생한다. 1의 '개수'를 반환하는 것이 문제의 조건이므로, 이를 기준으로 비트열의 규칙성을 찾아본다.

 

---

 

먼저 구하고자 하는 범위의 1의 개수는 다음과 같이 나타낼 수 있다.

 

l번째부터 r번째까지 1의 개수 = 1번째부터 r번째까지 1의 개수 - 1번째부터 l - 1번째까지 1의 개수

 

폐구간 [l, r]이므로 l - 1번째까지의 1의 개수를 뺀다.

 

---

 

유사 칸토어 비트열의 특성 상 임의의 수 x에 대하여, x번째 수 앞에는 특정 패턴들이 온다. 예를 들면 다음과 같다.

 

5^0 형태의 패턴 (1)

 

5^1 형태의 패턴 (11011)

 

5^2 형태의 패턴 (11011)(11011)(00000)(11011)(11011)

 

5^3 형태의 패턴 (11011)(11011)(00000)(11011)(11011)(11011)(11011)(00000)(11011)(11011) ...

 

이 패턴들은 5의 거듭제곱 형태를 띈다. 또한 5^n 형태의 패턴은 4^n개의 1을 가진다. 반복 시행을 통해 이러한 규칙성을 찾을 수 있다.

 

---

 

예를 들어, 27번째까지 1의 개수를 구해보자.

 

(11011)(11011)(00000)(11011)(11011)(11011) ...

 

27 = 25 + 2와 같이 나타낼 수 있고, 이는 1 * (5^2) + 0 * (5^1) + 2 * (5^0)의 형태로 나타낼 수 있다. 5^n 형태의 패턴은 4^n개의 1을 가지므로, 1 * (4^2) + 0 * (4^1) + 2 * (4^0) = 18이다. 이와 같은 형태로 폐구간 [l, r]에 대해 연산을 수행하면 답을 도출할 수 있다.

 

이처럼 해당 숫자를 5진수로 나타내는 것이 이 문제의 핵심이다. 단, 다음과 같은 예외 사항이 존재한다.

 

1. 패턴이 3개 이상 앞에 올 경우
2. l 또는 r이 패턴의 가운데 부분(0이 연속적으로 나타나는 부분)에 위치할 경우

 

---

 

예시로 41번째까지 1의 개수를 구해보자.

 

(11011)(11011)(00000)(11011)(11011)(11011)(11011)(00000)(11011)

 

41을 5진수로 나타내면 131이다. 이는 1 * (5^2) + 3 * (5^1) + 1 * (5^0) 이고, 위 방식대로 1의 개수를 계산하면 1 * (4^2) + 3 * (4^1) + 1 * (4^0) = 29개이다. 그러나 실제로 1의 개수는 25개이다.

 

특정 패턴 3개 또는 4개가 앞에 올 경우 (00000)과 같은 패턴의 가운데 부분을 포함하고 있으므로 이를 제외시켜야 한다. 따라서 3개일 경우 2개 만큼의 1의 개수를 가지고, 4개일 경우 3개 만큼의 1의 개수를 가진다.

 

 

예시로 38번째까지 1의 개수를 구해보자.

 

(11011)(11011)(00000)(11011)(11011)(11011)(11011)(00000)(11011)

 

38을 5진수로 나타내면 123이다. 이는 1 * (5^2) +  2 * (5^1) + 3 * (5^0) 이고, 위 방식대로 1의 개수를 계산하면 1 * (4^2) + 2 * (4^1) + 3 * (4^0) = 27개이다. 그러나 실제로 1의 개수는 24개이다.

 

유사 칸토어 비트열은 특정 패턴을 크게 3등분으로 볼 수 있으며, 그 중 가운데 부분은 0으로 이루어져 있다. 즉 특정 패턴 2개가 앞에 오면 그 다음은 0에 위치할 수 밖에 없다는 것이다. 이는 모든 패턴에 대해서 동일하게 적용된다.

 

(11011)(11011)(00000)(11011)(11011)

 

위와 같이 5^1 패턴이 2개 오면 그 다음은 0이 1 * (5^1)개인 패턴이 온다. 나머지 항의 합은 a * 5^0 이고, 이는 1 * (5^1)보다 항상 작다. 따라서 특정 패턴이 2개 온 이후로 l 또는 r 번째까지 모든  수는 0이다.

 

5진수는 a * 5^n + b * 5^(n-1) + ... + e * 5^0 와 같이 표현된다. 5진수의 특성 상 '1 * 5^(n-1) > 차수가 n-1 미만인 나머지 항들의 합'을 만족한다. 따라서 5진수로 변환한 수의 특정 자리수가 2라면, 그 아래 모든 자리수에 대해서 1의 개수를 고려할 필요가 없다.

 

풀이

function solution(n, l, r) {
    var answer = 0;
    
    let quinaryL = (l - 1).toString(5);
    let quinaryR = r.toString(5);
    
    let quinaryLcnt = 0;
    let quinaryRcnt = 0;
    
    for (let i = 0; i < quinaryL.length; i++) {
        let exponent = quinaryL.length - (i + 1);
        let digitNum = parseInt(quinaryL[i]);
        if (digitNum > 2) {
            quinaryLcnt += (digitNum - 1) * (4 ** exponent);
        }
        else if (digitNum == 2) {
            quinaryLcnt += digitNum * (4 ** exponent);
            break;
        }
        else {
            quinaryLcnt += digitNum * (4 ** exponent);
        }
    }
    
    for (let i = 0; i < quinaryR.length; i++) {
        let exponent = quinaryR.length - (i + 1);
        let digitNum = parseInt(quinaryR[i]);
        if (digitNum > 2) {
            quinaryRcnt += (digitNum - 1) * (4 ** exponent);
        }
        else if (digitNum == 2) {
            quinaryRcnt += digitNum * (4 ** exponent);
            break;
        }
        else {
            quinaryRcnt += digitNum * (4 ** exponent);
        }
    }
    
    answer = quinaryRcnt - quinaryLcnt;
    
    return answer;
}