C++에서 모든 1을 하나로 그룹화하기 위한 최소 스왑 횟수 구하기

문제 정의

0과 1로만 구성된 배열이 주어졌을 때, 배열에 있는 모든 1을 서로 인접한 하나의 그룹으로 모으기 위해 필요한 최소 스왑(교환) 횟수를 구하는 것이 이번 문제의 목표입니다.

예시

입력 배열이 {1, 0, 1, 1, 0, 1}이라면 필요한 스왑 횟수는 1회입니다. 첫 번째 0과 마지막 1의 위치를 서로 교환하면 모든 1이 연속된 형태로 배치됩니다.

알고리즘

• 배열에 포함된 1의 총 개수를 셉니다.
• 1의 개수를 x라고 할 때, 길이가 x인 부분 배열 중에서 1이 가장 많이 포함된 구간을 찾습니다.
• 필요한 최소 스왑 횟수는 해당 구간(1이 가장 많은 길이 x의 부분 배열)에 들어 있는 0의 개수와 같습니다.

동작 원리

이 알고리즘은 슬라이딩 윈도우(sliding window) 기법과 누적 합(prefix sum) 배열을 활용합니다. 먼저 배열 전체에서 1의 개수를 세어 윈도우 크기를 정한 뒤, 누적 합 배열을 이용하면 각 윈도우 구간에 포함된 1의 개수를 O(1) 시간에 구할 수 있습니다. 1이 가장 밀집된 구간을 찾으면 그 구간의 0만 배열의 다른 위치에 있는 1과 교환하면 되므로, 구간 내 0의 개수가 곧 최소 스왑 횟수가 됩니다. 전체 시간 복잡도는 O(n)입니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
int getMinSwaps(int *arr, int n) {
    int oneCnt = 0;
    for (int i = 0; i < n; ++i) {
        if (arr[i] == 1) {
            ++oneCnt;
        }
    }
    int x = oneCnt;
    int maxOnes = INT_MIN;
    vector<int> preCompute(n, 0);
    if (arr[0] == 1) {
        preCompute[0] = 1;
    }
    for (int i = 1; i < n; ++i) {
        if (arr[i] == 1) {
            preCompute[i] = preCompute[i - 1] + 1;
        } else {
            preCompute[i] = preCompute[i - 1];
        }
    }
    for (int i = x - 1; i < n; ++i) {
        if (i == (x - 1)) {
            oneCnt = preCompute[i];
        } else {
            oneCnt = preCompute[i] - preCompute[i - x];
        }
        if (maxOnes < oneCnt) {
            maxOnes = oneCnt;
        }
    }
    return x - maxOnes;
}
int main() {
    int arr[] = {1, 0, 1, 1, 0, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Minimum swap count = " << getMinSwaps(arr, n) << endl;
    return 0;
}

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

출력 결과

Minimum swap count = 1