C++ 이진 문자열에서 왼쪽은 모두 1, 오른쪽은 모두 0이 되도록 만드는 최소 뒤집기 횟수 구하기

문제 설명

이진(binary) 문자열이 하나 주어집니다. 이 문자열을 임의의 위치에서 두 부분으로 나누어 왼쪽 부분은 모두 1, 오른쪽 부분은 모두 0이 되도록 만들어야 하며, 이때 필요한 최소 뒤집기(flips) 횟수를 구하는 것이 과제입니다.

예시

주어진 이진 문자열이 0010101라고 가정해 보겠습니다. 이 문자열에는 1비트가 3개, 0비트가 4개 포함되어 있습니다. 아래와 같이 총 4개의 비트를 뒤집으면 왼쪽은 모두 1, 오른쪽은 모두 0인 형태가 됩니다.

0010101

뒤집기를 수행한 후의 문자열은 다음과 같습니다.

1110000

접근 방법(알고리즘)

• 문자열을 왼쪽에서 오른쪽으로 순회하면서, 각 위치까지 등장한 0의 개수(해당 위치까지를 왼쪽 부분으로 삼을 때 1로 바꿔야 할 횟수)를 미리 계산해 둡니다.
• 문자열을 오른쪽에서 왼쪽으로 순회하면서, 각 위치부터 끝까지 등장한 1의 개수(해당 위치부터를 오른쪽 부분으로 삼을 때 0으로 바꿔야 할 횟수)를 미리 계산해 둡니다.
• 모든 분할 지점에 대해 (왼쪽 부분의 0 뒤집기 횟수 + 오른쪽 부분의 1 뒤집기 횟수)의 합을 구하고, 그중 최솟값을 정답으로 반환합니다.

각 배열을 한 번씩 채우고 마지막으로 한 번 더 순회하므로, 이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)입니다.

C++ 구현 예제

#include <iostream>
#include <string>
#include <climits>
using namespace std;
int minFlips(string binaryString) {
    int n = binaryString.length();
    int flipCnt, zeroFlips[n], oneFlips[n];
    flipCnt = 0;
    for (int i = 0; i < n; ++i) {
       if (binaryString[i] == '0') {
          ++flipCnt;
       }
       zeroFlips[i] = flipCnt;
    }
    flipCnt = 0;
    for (int i = n - 1; i >= 0; --i) {
       if (binaryString[i] == '1') {
          ++flipCnt;
       }
       oneFlips[i] = flipCnt;
    }
    int minFlips = INT_MAX;
    for (int i = 1; i < n; ++i) {
       int sum = zeroFlips[i - 1] + oneFlips[i]; if (sum < minFlips) {
          minFlips = sum;
       }
    }
    return minFlips;
}
int main() {
    string binaryString = "0010101";
    cout << "Minimum flips: " << minFlips(binaryString) <<
    endl;
    return 0;
}

코드 동작 원리

zeroFlips[i]에는 인덱스 0부터 i까지의 0 개수가, oneFlips[i]에는 인덱스 i부터 문자열 끝까지의 1 개수가 저장됩니다. 분할 지점 i를 기준으로 왼쪽(0 ~ i-1)의 0을 모두 1로 바꾸는 횟수와 오른쪽(i ~ n-1)의 1을 모두 0으로 바꾸는 횟수를 더한 값이 해당 분할에서 필요한 총 뒤집기 횟수입니다. 가능한 모든 분할 지점을 검사하여 그 최솟값을 구해 반환합니다.

출력 결과

위 프로그램을 컴파일하여 실행하면 다음과 같은 결과가 출력됩니다.

Minimum flips: 4