문제 정의
양의 정수로 이루어진 배열 arr[]이 주어졌을 때, 아래 조건을 모두 만족하도록 배열을 나누는 최소한의 집합(set) 개수를 구하는 것이 목표입니다.
- 하나의 집합에는 최대 2개의 원소만 포함할 수 있으며, 두 원소는 반드시 인접해 있을 필요는 없습니다.
- 집합에 속한 원소들의 합은 주어진 값(key) 이하여야 합니다. 편의상 key는 항상 배열의 최댓값보다 크거나 같다고 가정합니다.
예시
배열이 arr[] = {1, 2, 3, 4}이고 k = 5라고 가정해 보겠습니다. 이 경우 다음과 같이 2개의 집합으로 나눌 수 있습니다.
{1, 4} 와 {2, 3}
두 집합 각각의 합은 5로, 조건을 정확히 만족하며 이것이 가능한 최소 개수입니다.
알고리즘: 투 포인터(Two Pointer) 기법
이 문제는 정렬과 투 포인터를 활용하면 효율적으로 해결할 수 있습니다.
- 먼저 배열을 오름차순으로 정렬합니다.
- 정렬된 배열의 양쪽 끝에 두 개의 포인터(i는 가장 작은 값, j는 가장 큰 값을 가리킴)를 둡니다.
- arr[i] + arr[j]가 key 이하라면, 두 원소를 하나의 집합으로 묶고 j를 감소시켜 다음 후보로 넘어갑니다.
- 만약 두 원소의 합이 key를 초과한다면, 가장 큰 원소(arr[j])는 어떤 원소와도 짝을 지을 수 없으므로 단독으로 하나의 집합을 구성하고 j만 감소시킵니다.
동작 원리
가장 작은 값과 가장 큰 값을 짝지어 보는 전략이 유효한 이유는, 가장 큰 값조차 가장 작은 값과 합쳐질 수 없다면 다른 어떤 값과도 합쳐질 수 없기 때문입니다. 따라서 매 단계에서 최선의 선택을 하는 그리디(Greedy) 방식으로 최적해를 보장할 수 있습니다.
C++ 구현 코드
#include <iostream>
#include <algorithm>
using namespace std;
int getMinSets(int *arr, int n, int key) {
int i, j;
sort (arr, arr + n);
for (i = 0, j = n - 1; i <= j; ++i) {
if (arr[i] + arr[j] <= key) {
--j;
}
}
return i;
}
int main() {
int arr[] = {1, 2, 3, 4};
int key = 5;
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum set = " << getMinSets(arr, n, key) << endl;
return 0;
}실행 결과
위 프로그램을 컴파일하여 실행하면 다음과 같은 결과가 출력됩니다.
Minimum set = 2
복잡도 분석
- 시간 복잡도: 정렬에 O(n log n), 이후 투 포인터 탐색에 O(n)이 소요되므로 전체 시간 복잡도는 O(n log n)입니다.
- 공간 복잡도: 추가 메모리 없이 제자리 정렬을 사용하므로 O(1)입니다.