문제 설명
0과 1로만 구성된 길이 n의 정수 배열이 주어집니다. 배열이 분할(partitioned) 상태, 즉 앞쪽에는 모든 0이, 뒤쪽에는 모든 1이 오도록 만들기 위해 필요한 최소 토글 횟수(0을 1로, 또는 1을 0으로 바꾸는 연산)를 구하는 것이 목표입니다.
예시
예를 들어 arr[] = {1, 0, 0, 1, 1, 1, 0}이라면 필요한 토글 횟수는 2입니다. 즉, 첫 번째 원소인 1을 0으로 바꾸고, 마지막 원소인 0을 1로 바꾸면 됩니다.
변환 결과: {0, 0, 0, 1, 1, 1, 1}
접근 방법
- 문제를 자세히 살펴보면, 0부터 n-1 사이에 반드시 하나의 분할 지점이 존재한다는 것을 알 수 있습니다. 이 지점을 기준으로 왼쪽에는 모든 0이, 오른쪽에는 모든 1이 위치해야 합니다.
- 각 지점 i에 대해, 왼쪽 부분(처음 ~ i번째)에서 1의 개수와 오른쪽 부분에서 0의 개수를 더하면 해당 지점을 기준으로 할 때 필요한 토글 횟수가 됩니다.
- 이를 효율적으로 계산하기 위해 누적 합(prefix sum) 기법을 활용해 왼쪽부터 0의 개수를 미리 세어 둡니다.
구현 예제
#include <bits/stdc++.h>
using namespace std;
int getMinToggles(int *arr, int n) {
// zeroCnt[i] = arr[0..i-1] 범위 내 0의 개수 (누적 합)
int zeroCnt[n + 1] = {0};
for (int i = 1; i <= n; ++i) {
if (arr[i - 1] == 0) {
zeroCnt[i] = zeroCnt[i - 1] + 1;
} else {
zeroCnt[i] = zeroCnt[i - 1];
}
}
int result = n;
// 각 분할 지점 i마다 필요한 토글 수를 계산
for (int i = 1; i <= n; ++i) {
// 왼쪽 i개 원소 중 1의 개수: i - zeroCnt[i]
// 오른쪽 (n-i)개 원소 중 0의 개수: zeroCnt[n] - zeroCnt[i]
result = min(result, i - zeroCnt[i] + zeroCnt[n] - zeroCnt[i]);
}
return result;
}
int main() {
int arr[] = {1, 0, 0, 1, 1, 1, 0};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum toggles = " << getMinToggles(arr, n) << endl;
return 0;
}
실행 결과
위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.
Minimum toggles = 2
동작 원리 상세 설명
배열 {1, 0, 0, 1, 1, 1, 0}에서 전체 0의 개수는 3개입니다. 분할 지점을 i = 3으로 설정하면 다음과 같습니다.
- 왼쪽 3개 원소 {1, 0, 0} 중 1의 개수는 1개 → 1회 토글 필요
- 오른쪽 4개 원소 {1, 1, 1, 0} 중 0의 개수는 1개 → 1회 토글 필요
따라서 총 2회의 토글만으로 배열을 {0, 0, 0, 1, 1, 1, 1} 형태로 만들 수 있으며, 이것이 가능한 모든 분할 지점 중 최솟값입니다.
복잡도 분석
- 시간 복잡도: O(n) — 배열을 두 번 순회하므로 선형 시간에 해결됩니다.
- 공간 복잡도: O(n) — 0의 개수를 저장하는 누적 합 배열이 필요합니다.