JavaScript로 숫자의 이진 표현에서 1의 개수 효율적으로 계산하기

문제 정의

정수 하나를 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다. 이 함수는 0부터 num까지(양 끝값 포함)의 모든 숫자에 대한 배열을 생성해야 하며, 배열의 각 요소는 해당 숫자의 이진 표현에 포함된 1의 개수가 되어야 합니다.

예를 들어, 함수의 입력이 다음과 같다면 −

const num = 4;

출력은 다음과 같아야 합니다 −

const output = [0, 1, 1, 2, 1];

출력 설명

0은 이진수로 '0'이므로 1을 포함하지 않고, 1은 '1'이므로 1개, 2는 '10', 3은 '11'(2개), 4는 '100'(1개)입니다. 즉, 각 숫자의 이진 표현에 따라 1의 개수가 결정됩니다.

예제 코드

이 문제를 해결하는 코드는 다음과 같습니다 −

const num = 4;
const mapBinary = (num = 0) => {
    if (num === 0){
        return [0];
    };
    const res = [0];
    for (let i = 1; i <= num; i++) {
        const n = i % 2 === 0 ? res[i/2] : res[Math.floor(i/2)] + 1;
        res.push(n);
    };
    return res;
};

코드 설명

비트를 계산할 때 아래의 규칙들을 활용하면 문제를 훨씬 쉽게 해결할 수 있습니다.

• numberOfBits(n) === numberOfBits(2 * n): 어떤 수를 두 배로 만들면 이진 표현 뒤에 0이 하나 추가될 뿐이므로, 1의 개수는 변하지 않습니다.

• n이 짝수인 경우: 짝수의 마지막 비트는 항상 0입니다. 따라서 n의 1의 개수는 n/2의 1의 개수와 동일합니다.

• n이 홀수인 경우: 홀수의 결과는 (n-1)/2의 마지막 비트를 1로 바꾼 것과 같으므로, numberOfBits(n) === numberOfBits(Math.floor(n / 2)) + 1 공식이 성립합니다.

이러한 점화 관계를 활용하면 이미 계산된 값을 재사용하는 동적 계획법(DP) 방식으로 문제를 풀 수 있습니다. 각 숫자를 직접 이진수로 변환하는 방식은 O(n log n)의 시간이 걸리지만, 이 접근법은 각 숫자를 한 번씩만 처리하므로 O(n)의 시간 복잡도로 더욱 효율적입니다.

실행 결과

콘솔에 출력되는 최종 결과는 다음과 같습니다 −

[ 0, 1, 1, 2, 1 ]