C++에서 비트 하나만 뒤집어 만들 수 있는 가장 긴 연속된 1의 길이 구하기

문제 개요

정수 n이 하나 주어져 있을 때, 이 수의 이진 표현에서 단 한 개의 비트만 0에서 1로 뒤집어(flipping) 얻을 수 있는 가장 긴 연속된 1의 시퀀스를 찾는 것이 목표입니다.

예를 들어 숫자가 13이라면 이진 표현은 1101입니다. 여기서 0인 비트 하나를 1로 바꾸면 1111이 되며, 이것이 만들 수 있는 가장 긴 1의 시퀀스입니다.

접근 방법

이 문제를 해결하려면 주어진 숫자의 비트를 오른쪽(LSB)부터 하나씩 순회하면서 다음 두 가지 값을 추적해야 합니다.

curr: 현재 이어지고 있는 1의 시퀀스 길이
prev: 0을 하나 사이에 두고 바로 앞에 있던 1의 시퀀스 길이

순회 중 0을 만나면 그다음 비트가 무엇인지에 따라 prev를 갱신합니다. 다음 비트가 1이면 prev를 curr 값으로 설정하고, 0이면 prev를 다시 0으로 초기화합니다. 매 단계마다 prev + curr의 최대값을 기록해 두면, 마지막에 플립되는 비트 하나(+1)를 더해 정답을 구할 수 있습니다.

또한 모든 비트가 이미 1로 채워져 있는 경우(~number == 0)에는 뒤집을 필요가 없으므로 int의 전체 비트 크기(32)를 그대로 반환합니다.

C++ 구현 예제

#include <iostream>
using namespace std;

int singleFlipMaxOnes(unsigned number) {
    if (~number == 0)   // 모든 비트가 이미 1인 경우
        return 8 * sizeof(int);

    int curr = 0, prev = 0, max_size = 0;
    while (number != 0) {
        if ((number & 1) == 1)
            curr++;
        else {                                    // 0을 만난 경우
            prev = (number & 2) == 0 ? 0 : curr;  // 다음 비트에 따라 prev 결정
            curr = 0;
        }
        max_size = max(prev + curr, max_size);
        number >>= 1;
    }
    return max_size + 1;                          // 플립한 비트 1개 추가
}

int main() {
    cout << "연속된 1의 최대 길이: " << singleFlipMaxOnes(13);
}

실행 결과

연속된 1의 최대 길이: 4

동작 과정 살펴보기 (예시: 13 = 1101)

13의 이진 표현은 1101이며, LSB부터 비트를 읽으면 1 → 0 → 1 → 1 순서입니다.

첫 번째 비트(1): curr = 1 → 최대값 후보 = 0 + 1 = 1
두 번째 비트(0): 다음 비트가 1이므로 prev = 1, curr = 0 → 최대값 후보 = 1
세 번째 비트(1): curr = 1 → 최대값 후보 = prev(1) + curr(1) = 2
네 번째 비트(1): curr = 2 → 최대값 후보 = 1 + 2 = 3

루프가 끝난 뒤 3에 플립할 비트 1개를 더해 최종 답은 4가 됩니다.

복잡도 분석

시간 복잡도: O(b) — b는 숫자의 비트 수(int 기준 최대 32)
공간 복잡도: O(1) — 추가 변수 몇 개만 사용