이 튜토리얼에서는 배열의 두 부분 집합 사이의 최대 차이를 구하는 프로그램을 작성하는 방법을 살펴보겠습니다.
문제 정의
임의의 정수들이 하나 또는 두 개씩 포함된 배열이 주어집니다. 우리의 과제는 이 배열을 두 개의 부분 집합으로 나누어 다음 조건을 만족시키는 것입니다.
- 두 부분 집합의 합의 차이가 최대가 되어야 합니다.
- 어떤 부분 집합에도 중복된 숫자가 포함되어서는 안 됩니다.
접근 방법
이 문제는 다음과 같은 단계로 해결할 수 있습니다.
- 배열을 순회하며 각 요소가 배열의 다른 위치에도 등장하는지(중복 여부) 확인합니다.
- 중복되는 요소 쌍은 두 값을 모두 0으로 만들어 계산에서 제외합니다. 이를 통해 어떤 부분 집합에도 동일한 숫자가 두 번 포함되지 않도록 보장합니다.
- 중복이 아닌 요소는 양수일 경우 첫 번째 부분 집합에, 음수일 경우 두 번째 부분 집합에 더합니다.
- 마지막으로 두 부분 집합 합의 절댓값 차이를 결과로 반환합니다.
양수는 한쪽 집합에 모으고 음수는 반대쪽 집합에 모으면 두 합의 차이가 자연스럽게 최대화되므로, 이러한 배치 전략이 최적의 답을 보장합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
//두 부분 집합의 최대 차이를 구하는 함수
int maxDiff(int arr[], int n) {
int SubsetSum_1 = 0, SubsetSum_2 = 0;
for (int i = 0; i <= n - 1; i++) {
bool isSingleOccurance = true;
for (int j = i + 1; j <= n - 1; j++) {
if (arr[i] == arr[j]) {
isSingleOccurance = false;
arr[i] = arr[j] = 0;
break;
}
}
if (isSingleOccurance) {
if (arr[i] > 0)
SubsetSum_1 += arr[i];
else
SubsetSum_2 += arr[i];
}
}
return abs(SubsetSum_1 - SubsetSum_2);
}
int main() {
int arr[] = { 4, 2, -3, 3, -2, -2, 8 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum Difference = " << maxDiff(arr, n);
return 0;
}
실행 결과
Maximum Difference = 20
동작 원리 분석
예제 입력 { 4, 2, -3, 3, -2, -2, 8 }을 기준으로 코드의 동작을 살펴보겠습니다.
- -2는 배열에 두 번 등장하므로 중복으로 처리되어 계산에서 제외됩니다.
- 양수 4, 2, 3, 8은 첫 번째 부분 집합에 더해져 합계가 17이 됩니다.
- 음수 -3은 두 번째 부분 집합에 더해집니다.
- 따라서 최대 차이는 |17 − (−3)| = 20입니다.
시간 복잡도
위 코드는 중복 여부를 확인하기 위해 이중 루프를 사용하므로 시간 복잡도는 O(n²)입니다. 배열을 먼저 정렬한 뒤 인접한 요소만 비교하면 O(n log n)으로 최적화할 수 있습니다.