[TIL #18] 2개 이하로 다른 비트

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

프로그래머스

 

비트를 다루는 문제.

결국 현대의 컴퓨터는 이진수로 동작하기 때문에,

비트 연산에 대해 잘 알아둘 필요가 있다.

그만큼 그 성질을 잘 이해하고 사용할 필요가 있다.

이번에도 엄청 헤맸다...

 

일단 이 문제는 정수 ``x``에 대해 해밍거리가 2 이하인 수 중에서 가장 작은 수를 찾는 문제다.

즉, 몇 개의 비트가 차이가 나는지 비교해 볼 필요가 있다.

C++이라면 ``std::bitset::count`` 같은 내장 함수로 비트의 개수를 가져올 수 있지만 JS엔 없는 것 같다.

그래서 일단 각 거리 별 비트마스크를 생성해 그걸 통해 XOR연산을 하며 값들을 찾기로 했다.

그 코드는 다음과 같다.

 

// 해밍거리가 1이나 2인 수들이 필요
// Brian Kernighan's 알고리즘 대신
// 각 거리를 위한 비트마스크를 만들어 비트 차이 계산

function solution(numbers) {
    const answer = [];

    // 비트 마스크 사전 생성
    const bitMasks1 = [];
    const bitMasks2 = [];
    const maxBits = 50; // 10^15는 50비트로 표현 가능

    // 거리 1을 위한 비트마스크 생성
    for (let i = 0; i < maxBits; i++) {
        bitMasks1.push(1n << BigInt(i));
    }

    // 거리 2를 위한 비트마스크 생성
    for (let i = 0; i < maxBits; i++) {
        for (let j = i + 1; j < maxBits; j++) {
            bitMasks2.push((1n << BigInt(i)) | (1n << BigInt(j)));
        }
    }

    // 거리 1인 마스크 먼저 검사 후, 거리 2인 마스크 검사
    for (let i = 0; i < numbers.length; i++) {
        const num = BigInt(numbers[i]);
        let minCandi = null;

        // 거리 1 검사
        // XOR 연산을 통해 비트 N개가 반전된 새로운 수 생성
        for (let mask of bitMasks1) {
            const candi = num ^ mask;
            if (candi > num) {
                if (minCandi === null || candi < minCandi) {
                    minCandi = candi;
                }
            }
        }

        // 거리 2 검사
        if(minCandi !== null) {
            for (let mask of bitMasks2) {
                const candi = num ^ mask;
                if (candi > num) {
                    if (minCandi === null || candi < minCandi) {
                        minCandi = candi;
                    }
                }
            }
        }

        // 최소 후보가 존재하면 그 수를 변환, 아니면 null
        answer.push(minCandi !== null ? Number(minCandi) : null);
    }

    return answer;
}

결국은 터졌다.

나름 무식하게 브루트 포스로 하지 않았기에 나쁘지 않을 거라고 생각했는데...

 

사실상 시간만 보면 전부 실패라는 느낌.

이렇게 시간이 걸려선 안될 일이라고 생각했다.

``BigInt``를 사용하지 않으면 뒤쪽의 테스트에서 에러가 생긴다.

분명 ``10^15``는 ``Number``의 범위 안에 있을 텐데...

계속 문제가 생기므로 다른 접근법을 찾아야 했다.

뭔가 심플하게 나올 규칙성이 있지 않을까 고민했다.

 

 

문제를 다시 잘 보자.

정수 ``x``에 대해 해밍거리가 2 이하인 ``x``보다 큰 수를 찾아야 한다.

만약 최우측 비트가 0이라면?

그냥 그 부분을 1로 만들면 된다.

기존 수 보다 1만 커지면서 조건을 만족한다.

짝수는 이걸로 필터링 가능하다.

그럼 홀수는?

 

홀수에도 규칙이 있다.

문제에서 제시하는 예시를 보자.

``0111``에 ``1011``이 정답이다.

다른 예시로 ``1111``을 생각해 보자.

이 경우 정답은 ``10111``이 된다.

 

``1011`` - ``0111`` = ``100`` = ``2 ^ 2``

``10111`` - ``1111`` = ``1000`` = ``2 ^ 3``

이러면 규칙성이 보이는 것 같다.

정수 ``x``의 비트에서 1인 연속되는 횟수만큼 에서 1을 빼고 그 수만큼 2를 제곱한 값이 키가 된다.

1을 뺀 수를 ``c``라고 할 때, 식은 다음과 같은 형태가 된다.

$$ f(x) = x + 2^{c-1} $$

 

이걸 코드로 옮기면 다음과 같다.

// 연속된 1의 개수를 세는 함수
function countTrail(x) {
    let count = 0;
    while ((x & 1n) === 1n) {
        count += 1;
        x >>= 1n;
    }
    return count;
}

function solution(numbers) {
    // 각 숫자에 대해 f(x)를 계산
    return numbers.map((num) => {
        let x = BigInt(num);
        if (x % 2n === 0n) {    // 짝수인 경우
            return Number(x + 1n);
        } else {    // 홀수인 경우      
            let c = countTrail(x);
            // c가 1이여도 x + 1이 된다.
            let increment = 1n << BigInt(c - 1);
            return Number(x + increment);
        }
    });
}

복잡할 것도 없고 엄청 간결해졌다.

 

시간도 잘 나왔다.

비트에서의 해밍거리가 2인 문제는 앞으로도 이를 응용해서 풀 수 있을 것 같다.

3부터는 확실히 복잡해질 것 같다는 느낌이 든다...