C++로 이진 문자열을 교대 패턴으로 만드는 최소 뒤집기 횟수 구하기

예를 들어 이진 문자열 "10011"이 주어졌다고 가정해 보겠습니다. 이 문자열을 교대(alternate) 패턴의 이진 문자열로 만들려면 최소 2개의 문자를 뒤집어 "10101"로 바꿔야 합니다.

문제 접근 방법

교대 이진 문자열에는 두 가지 가능한 형태가 있습니다. '0'으로 시작하는 경우(01010...)와 '1'로 시작하는 경우(10101...)입니다. 따라서 두 경우 각각에 대해 필요한 뒤집기 횟수를 계산한 뒤, 그중 더 작은 값을 반환하면 됩니다.

구체적인 예를 통해 살펴보겠습니다.

입력

binary = "10011"

출력

2

문자열을 '0'으로 시작하는 교대 패턴(01010)으로 만들려면 3번의 뒤집기가 필요하고, '1'로 시작하는 교대 패턴(10101)으로 만들려면 2번의 뒤집기만 필요합니다. 따라서 정답은 최솟값인 2가 됩니다.

알고리즘

1. 이진 문자열을 초기화합니다.
2. '1'로 시작하는 교대 문자열을 만들기 위해 필요한 뒤집기 횟수를 계산합니다.
3. 마찬가지로 '0'으로 시작하는 교대 문자열을 만들기 위해 필요한 뒤집기 횟수를 계산합니다.
4. 위에서 구한 두 값 중 최솟값을 찾습니다.
5. 최솟값을 출력합니다.

C++ 구현

다음은 위 알고리즘을 C++로 구현한 코드입니다.

#include <bits/stdc++.h>
using namespace std;
char flip(char binaryDigit) {
    return binaryDigit == '0' ? '1' : '0';
}
int getFlipCountToAlternateString(string binary, char expected) {
    int flipCount = 0;
    for (int i = 0; i < binary.length(); i++) {
        if (binary[i] != expected) {
            flipCount++;
        }
        expected = flip(expected);
    }
    return flipCount;
}
int main() {
    string binary = "10011";
    cout << min(getFlipCountToAlternateString(binary, '0'), getFlipCountToAlternateString(binary, '1')) << endl;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

2

코드 설명

getFlipCountToAlternateString 함수는 기대하는 시작 문자(expected)를 인자로 받아, 문자열의 각 위치에서 실제 문자와 기대 문자가 일치하지 않으면 뒤집기 횟수를 1씩 증가시킵니다. 한 글자를 확인할 때마다 기대 문자는 flip 함수를 통해 '0'과 '1' 사이를 번갈아 전환합니다. 이 방식을 사용하면 문자열을 단 한 번만 순회하면서 특정 교대 패턴에 맞추기 위한 뒤집기 횟수를 계산할 수 있습니다. 전체 수행 시간은 문자열 길이 n에 비례하는 O(n)이며, 추가 메모리를 사용하지 않으므로 공간 복잡도는 O(1)입니다.