프로그래머스 77885 - 2개 이하로 다른 비트 (Lv.5)

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

// 프로그래머스 77885 - 2개 이하로 다른 비트 (Lv.5)
// https://school.programmers.co.kr/learn/courses/30/lessons/77885

// 문제 설명
// 양의 정수 x에 대해 f(x)를 "x보다 크면서 x와 비트가 1개 또는 2개만 다른 수 중 가장 작은 수"로
// 정의한다. 예를 들어 f(2) = 3(2진수 10 -> 11, 1비트 차이), f(7) = 11(0111 -> 1011, 2비트 차이).
// 수의 배열 numbers가 주어질 때 각 원소에 대한 f(x)를 순서대로 담아 반환하라.

// 제약 조건
// 1 <= numbers 길이 <= 100,000
// 0 <= numbers[i] <= 10^15

// Example
// Input : [2, 7]
// Output: [3, 11]

// 접근 — 짝/홀 두 갈래 비트 규칙
// 후보를 x+1부터 하나씩 훑으면 최악에 수십억 번을 돈다. 규칙을 유도해 상수 시간에 끝낸다.
//
// 1) x가 짝수: 최하위 비트가 0이므로 그 자리만 켜면 x+1이 되고, x보다 크면서 1비트만 다르다.
//    1비트 차이 중 가장 작은 증가폭이므로 f(x) = x + 1로 확정.
//
// 2) x가 홀수: 최하위 비트부터 1이 연속되어 있어 +1은 그 1들을 전부 뒤집는다(7 -> 8은 4비트 차이).
//    x보다 커지려면 어딘가에서 0 -> 1이 반드시 필요하고, 그 자리가 낮을수록 증가폭이 작다.
//    따라서 오른쪽부터 처음 만나는 0비트 자리 p를 켠다(+2^p).
//    남은 1비트 예산으로는 켠 자리 바로 아래(2^(p-1), 반드시 1이다)를 끄는 것이 최대 감소.
//    정리하면 f(x) = x + 2^p - 2^(p-1) = x + 2^(p-1).
//    예: x = 7(0111) -> p = 3 -> 7 + 4 = 11(1011).
//
// 값이 10^15까지라 int(약 2.1 * 10^9)로는 넘치므로 long long을 쓴다.
// 시간 O(n * 비트수) = O(n * 50), 공간 O(n)

#include <vector>

using namespace std;

vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;

    for (long long x : numbers) {
        if (x % 2 == 0) {                   // 짝수는 마지막 0비트만 켜면 끝
            answer.push_back(x + 1);
            continue;
        }

        long long bit = 1;
        while (x & bit) bit <<= 1;          // 오른쪽부터 처음 만나는 0비트 자리
        answer.push_back(x + (bit >> 1));   // 그 자리를 켜고(+bit) 바로 아래를 끈다(-bit/2)
    }
    return answer;
}

정리

• 짝수와 홀수가 갈리는 이유는 +1이 몇 비트를 뒤집는가에 있다. 최하위 비트가 0이면 +1은 그 한 자리만 켜므로 곧바로 정답이지만, 홀수는 말단의 연속된 1을 전부 0으로 만들며 올림이 전파된다(7 → 8은 0111 → 1000으로 4비트 차이). 즉 “1 더하기”의 비트 비용이 상수가 아니라는 점이 문제의 전부다.
• 홀수 규칙의 최적성은 두 단계로 논증된다. (가) x보다 커지려면 바뀌는 비트 중 가장 높은 자리가 0 → 1이어야 하고, 그 자리가 낮을수록 증가폭이 작으므로 후보는 최하위 0비트 p 하나로 좁혀진다. (나) 남은 예산 1비트로는 값을 최대한 되돌려야 하는데, p 아래는 전부 1이므로 그중 가장 큰 자리인 2^(p-1)을 끄는 것이 최대 감소다. 결국 순증가분은 2^p - 2^(p-1) = 2^(p-1).
• 비트 탐색은 자릿수 대신 비트 값을 들고 다닌다 — while (x & bit) bit <<= 1;로 끝나면 bit가 곧 2^p이고, 아래 자리는 bit >> 1이라 시프트 횟수를 따로 세거나 pow를 쓸 필요가 없다. 같은 값을 한 줄로 얻는 ~x & (x + 1) 트릭도 있지만, 루프 쪽이 “오른쪽부터 0을 찾는다”는 의도를 그대로 드러낸다.
• 자료형 함정이 실질적인 감점 포인트다. 10¹⁵는 int 범위 밖이라 입력·출력·중간 변수 bit가 전부 long long이어야 한다. x가 2^50 - 1처럼 전부 1이면 bit가 2^50까지 올라가므로, 입력만 long long으로 바꾸고 bit를 int로 남기면 조용히 무한 루프나 오버플로로 넘어간다.
• 완전 탐색(x+1부터 팝카운트 비교)은 최악에 수십억 번을 돌아 효율성 테스트에서 그대로 탈락한다. 원소 10만 개 × 비트 50회 = 500만 회로 줄이는 규칙 유도 자체가 이 문제의 채점 기준이다. 커리큘럼 101번.
• 검증: 예제 [2, 7] → [3, 11] 통과, x = 0~3000 전 구간을 완전 탐색 정의(x보다 큰 수 중 XOR 팝카운트 ≤ 2인 최솟값)와 대조해 전건 일치, 10¹⁵ 및 2^50 - 1 경계 확인, 원소 10만 개 0.002초 (MSVC /O2 /std:c++17).

핵심 요약 — 짝수는 최하위 0비트를 켜서 x + 1이 곧 답이고, 홀수는 오른쪽부터 처음 만나는 0비트 2^p를 켜고 바로 아래 2^(p-1)을 꺼서 x + 2^(p-1)이 된다. 값이 10¹⁵까지라 bit를 포함한 모든 변수가 long long이어야 한다.