문제 설명
크기가 N으로 동일한 두 개의 배열이 주어졌을 때, 각 배열에서 원소를 하나씩 선택하여 최대한 많은 쌍(pair)을 만들어야 합니다. 단, 다음 조건을 만족해야 합니다.
- 각 배열의 원소는 최대 한 번만 사용할 수 있습니다.
- 쌍을 이루는 두 원소의 절댓값 차이는 주어진 값 K 이하여야 합니다.
예시
입력이 다음과 같다고 가정해 보겠습니다.
arr1[] = {3, 4, 5, 2, 1}
arr2[] = {6, 5, 4, 7, 15}
k = 3일 때, 절댓값 차이가 3 이하인 다음과 같은 4개의 쌍을 만들 수 있습니다.
(1, 4), (2, 5), (3, 6), (4, 7)
알고리즘
이 문제는 정렬과 탐욕적(Greedy) 기법을 활용하면 효율적으로 해결할 수 있습니다. 접근 방식은 다음과 같습니다.
- 두 배열을 모두 오름차순으로 정렬합니다.
- 첫 번째 배열의 각 원소에 대해, 두 번째 배열에서 아직 사용되지 않았으면서 절댓값 차이가 K 이하인 원소를 찾아 쌍을 만듭니다.
- 쌍이 형성되면 해당 원소는 사용 처리하고, 첫 번째 배열의 다음 원소로 넘어갑니다.
두 배열을 정렬한 뒤 작은 값부터 순서대로 매칭하면, 각 원소를 가장 유리하게 배정할 수 있어 전체 쌍의 개수가 최대화됩니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int getMaxUniquePairs(int *arr1, int *arr2, int n, int k) {
sort(arr1, arr1 + n);
sort(arr2, arr2 + n);
bool visited[n];
memset(visited, false, sizeof(visited));
int pairCnt = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (abs(arr1[i] - arr2[j]) <= k &&
visited[j] == false) {
++pairCnt;
visited[j] = true;
break;
}
}
}
return pairCnt;
}
int main() {
int arr1[] = {3, 4, 5, 2, 1};
int arr2[] = {6, 5, 4, 7, 15};
int n = sizeof(arr1) / sizeof(arr1[0]);
int k = 3;
cout << "최대 고유 쌍 = " << getMaxUniquePairs(arr1, arr2, n, k) << endl;
return 0;
}출력 결과
최대 고유 쌍 = 4
동작 원리 및 복잡도
위 코드에서는 visited 배열을 사용해 두 번째 배열의 원소가 이미 쌍을 이루었는지 추적합니다. 정렬된 상태에서 첫 번째 배열의 원소를 순회하며 매칭 가능한 가장 작은 값을 먼저 배정하므로, 탐욕적 선택이 항상 최적의 결과를 보장합니다.
- 시간 복잡도: O(N²) — 정렬 O(N log N)과 이중 반복문 O(N²)
- 공간 복잡도: O(N) — 방문 여부를 저장하는 visited 배열
N이 매우 큰 경우에는 투 포인터(Two Pointer) 기법을 활용하면 시간 복잡도를 O(N log N)까지 줄일 수 있습니다.