두 개의 정렬된 배열과 하나의 숫자 x가 주어졌을 때, 각 배열에서 원소를 하나씩 가져와 만든 쌍 중에서 그 합이 x에 가장 가까운 쌍을 찾는 문제입니다. 배열은 A1[0..m-1]과 A2[0..n-1]로 주어지며, 우리는 |A1[i] + A2[j] − x|의 절댓값이 최소가 되는 쌍 A1[i] + A2[j]를 구해야 합니다.
예를 들어 A1 = [1, 4, 5, 7], A2 = [10, 20, 30, 40], x = 32라고 한다면, 출력 결과는 1과 30이 됩니다. 1 + 30 = 31이며, 이는 x인 32와의 차이가 1로 가장 작기 때문입니다.
투 포인터(Two Pointer) 접근 방식
배열이 이미 정렬되어 있으므로, 브루트 포스 방식(O(m×n)) 대신 투 포인터 기법을 사용하면 O(m+n) 시간 복잡도로 문제를 해결할 수 있습니다. A1의 왼쪽 끝에서 시작하고, A2의 오른쪽 끝에서 시작하여 다음 단계를 따릅니다.
- diff 변수를 초기화합니다. 이 변수는 현재까지 찾은 쌍의 합과 x 사이의 최소 차이를 저장합니다.
- 두 포인터를 left := 0, right := n − 1로 초기화합니다.
- left < m이고 right ≥ 0인 동안 다음을 반복합니다.
- |A1[left] + A2[right] − x|가 현재 diff보다 작으면, diff와 결과 쌍을 갱신합니다.
- A1[left] + A2[right]가 x보다 작으면, 합을 키우기 위해 left를 1 증가시킵니다.
- 그렇지 않으면, 합을 줄이기 위해 right를 1 감소시킵니다.
- 반복이 끝나면 결과를 출력합니다.
C++ 구현 예제
#include<iostream>
#include<cmath>
using namespace std;
void findClosestPair(int A1[], int A2[], int m, int n, int x) {
int diff = INT_MAX;
int left_res, right_res;
int left = 0, right = n-1;
while (left<m && right>=0) {
if (abs(A1[left] + A2[right] - x) < diff) {
left_res = left;
right_res = right;
diff = abs(A1[left] + A2[right] - x);
}
if (A1[left] + A2[right] > x)
right--;
else
left++;
}
cout << "The closest pair is [" << A1[left_res] << ", "<< A2[right_res] << "]";
}
int main() {
int ar1[] = {1, 4, 5, 7};
int ar2[] = {10, 20, 30, 40};
int m = sizeof(ar1)/sizeof(ar1[0]);
int n = sizeof(ar2)/sizeof(ar2[0]);
int x = 32;
findClosestPair(ar1, ar2, m, n, x);
}실행 결과
The closest pair is [1, 30]
동작 원리 살펴보기
위 예제에서 탐색 과정을 추적해 보면 다음과 같습니다. 처음에는 A1[0]=1과 A2[3]=40의 합이 41로 x=32보다 크므로 right를 감소시킵니다. 이후 1+30=31이 되어 차이가 1로 갱신됩니다. 계속 진행하면 4+30=34(차이 2), 5+30=35(차이 3) 등으로 차이가 더 커지므로, 최종적으로 가장 가까운 쌍은 [1, 30]이 됩니다.
시간 복잡도
각 반복마다 left 또는 right 중 하나는 반드시 이동하므로, 전체 탐색은 최대 m + n번의 비교로 끝납니다. 따라서 시간 복잡도는 O(m + n)이며, 모든 조합을 검사하는 O(m × n) 방식보다 훨씬 효율적입니다. 공간 복잡도는 추가 배열 없이 상수 공간만 사용하므로 O(1)입니다.