C++에서 부분 배열을 한 번 뒤집어 0의 개수 최대화하기

문제 설명

이진 배열(binary array)이 주어졌을 때, 부분 배열(subarray)을 단 한 번 뒤집는(flip) 연산을 허용하여 배열 내 0의 개수를 최대화하는 것이 이 문제의 목표입니다.

여기서 뒤집기(flip) 연산이란 선택한 구간의 모든 0을 1로, 모든 1을 0으로 바꾸는 것을 의미합니다.

예를 들어 arr1 = {1, 1, 0, 0, 0, 0, 0}이라는 배열이 있다고 가정해 보겠습니다.

앞쪽에 있는 두 개의 1을 0으로 뒤집으면 다음과 같이 크기가 7인 배열을 얻을 수 있습니다.

{0, 0, 0, 0, 0, 0, 0}

접근 방법

이 문제의 핵심 아이디어는 다음과 같습니다.

1. 모든 부분 배열을 고려하여, 각 구간에 대해 (1의 개수) − (0의 개수) 값이 최대가 되는 구간을 찾습니다.
2. 이 값을 maxDiff라고 하면, 최종 정답은 원래 배열의 0의 개수 + maxDiff입니다.

그 이유는 간단합니다. 특정 구간을 뒤집으면 그 구간 안의 1은 0으로 바뀌어 전체 0의 개수에 더해지고, 반대로 그 구간 안의 0은 1로 바뀌어 0의 개수에서 빠져나가기 때문입니다. 따라서 (1의 개수) − (0의 개수) 차이가 가장 큰 구간을 뒤집는 것이 항상 최적의 선택이 됩니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

int getMaxSubArray(int *arr, int n){
    int maxDiff = 0;
    int zeroCnt = 0;
    for (int i = 0; i < n; ++i) {
        if (arr[i] == 0) {
            ++zeroCnt;
        }
        int cnt0 = 0;
        int cnt1 = 0;
        for (int j = i; j < n; ++j) {
            if (arr[j] == 1) {
                ++cnt1;
            }
            else {
                ++cnt0;
            }
            maxDiff = max(maxDiff, cnt1 - cnt0);
        }
    }
    return zeroCnt + maxDiff;
}

int main(){
    int arr[] = {1, 1, 0, 0, 0, 0, 0};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum subarray size = " << getMaxSubArray(arr, n) << endl;
    return 0;
}

실행 결과

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

Maximum subarray size = 7

시간 복잡도 분석

위 알고리즘은 두 개의 중첩된 반복문을 사용하므로 시간 복잡도는 O(n²)입니다. 만약 입력 배열의 크기가 매우 크다면, 최대 부분 배열 합을 찾는 데 널리 쓰이는 카데인 알고리즘(Kadane's Algorithm)을 응용하여 1을 +1, 0을 −1로 치환한 뒤 선형 시간 O(n)으로 최적화할 수 있습니다.