[프로그래머스] 148652 유사 칸토어 비트열(javascript)

문제

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

풀이

문제를 읽을 때, 제한 조건을 통해 불가능한 접근을 먼저 걸러내고 시작하려고 하는 편이다.

$1 \leq n \leq 20$ 이므로 최대 길이는 $5^{20}$ 이 된다. 이 정도 크기라면 문자열이나 배열로 직접 구성하는 방식은 현실적으로 불가능하다고 판단할 수 있다.

javascript의 Number 타입은 64-bit 부동소수점(IEEE 754)이며, 안전하게 표현할 수 있는 정수 범위는 $-(2^{53} - 1)$ 부터 $2^{53} - 1$ 까지이다. 따라서 $5^{20}$ 은 이 범위 내에 포함되므로, 수 계산 기반으로 접근하는 것이 문제 해결에 더 적합하다고 판단했다.

이후 수학적인 시선을 통해 문제를 다시 읽어보았고, 다음과 같은 인사이트를 얻을 수 있었다.

전체 구조는 5진수 기반의 패턴이다.
$f(n)$ 을 n에서의 1의 개수라고 하면, $f(0) = 1$ , $f(n) = 4 \cdot f(n-1)$ 이므로, 결국 $f(n) = 4^n$ 이다.

이 구조를 보고, merge sort에서 사용하는 divide and conquer 방식과 유사하게 접근할 수 있겠다고 판단했다. 다만 바로 구간 분할로 들어가기보다, 각 인덱스가 최종적으로 0인지 1인지 판별하는 로직을 먼저 구현해 검증해보았다. 간단한 판별식을 만들고 여러 값을 테스트해본 결과, 대부분의 케이스에서 올바르게 동작하는 것을 확인할 수 있었고, 해당 방식으로 제출을 진행했다. 결과적으로 시간 초과 없이 통과되었고, 정답으로 인정받을 수 있었다.

최종적인 실행 횟수는 $(r - l + 1) \cdot \log n$ 이며, 각 인덱스를 판별하는 비용은 동일하지만 전체를 순회하기 때문에 다소 비효율적이다. 문제의 구조를 블록 단위로 분할하는 방식으로 확장하면 divide and conquer 기반으로 $O(\log n)$ 까지 최적화할 수 있다.

개선점 적용 전 정답 코드

javascript

const isOne = (index) => {
    while (index) {
        if (index % 5 === 2) {
            return 0;
        }
        index = Math.floor(index / 5);
    }
    return 1;
}

const solution = (n, l, r) => {
    let ret = 0;
    
    for (let i = l - 1; i <= r - 1; i++) {
        ret += isOne(i);
    }
    
    return ret;
}

[프로그래머스] 148652 유사 칸토어 비트열(javascript)

문제

풀이

개선점 적용 전 정답 코드

Share this post