두 개의 정렬된 배열이 주어졌을 때, 각 배열에서 원소를 하나씩 선택해 만든 합이 특정 목표 값(target sum)에 가장 가까운 쌍(closest pair)을 찾는 문제는 알고리즘 학습과 코딩 테스트에서 자주 등장하는 대표적인 유형입니다. 이 문제는 투 포인터(Two Pointer) 기법을 활용하면 모든 조합을 일일이 확인하지 않고도 선형 시간 안에 효율적으로 해결할 수 있습니다.
투 포인터 알고리즘의 동작 원리
정렬된 두 배열에서 가장 가까운 쌍을 찾는 절차는 다음과 같습니다.
- 첫 번째 배열은 왼쪽 끝(l = 0)에서, 두 번째 배열은 오른쪽 끝(r = 마지막 인덱스)에서 탐색을 시작합니다.
- 두 원소의 합과 목표 값의 차이를 계산하고, 기존에 기록된 최소 차이보다 작으면 해당 쌍을 결과로 저장합니다.
- 합이 목표 값보다 크면 오른쪽 포인터 r을 한 칸 줄여 합을 낮추고, 그렇지 않으면 왼쪽 포인터 l을 한 칸 늘려 합을 높입니다.
- 어느 한쪽 포인터가 배열 범위를 벗어날 때까지 위 과정을 반복합니다.
Java 구현 예제
public class Demo {
void closest_pair(int my_arr_1[], int my_arr_2[], int arr_1_len, int arr_2_len, int sum){
int diff = Integer.MAX_VALUE;
int result_l = 0, result_r = 0;
int l = 0, r = arr_2_len - 1;
while (l < arr_1_len && r >= 0){
if (Math.abs(my_arr_1[l] + my_arr_2[r] - sum) < diff){
result_l = l;
result_r = r;
diff = Math.abs(my_arr_1[l] + my_arr_2[r] - sum);
}
if (my_arr_1[l] + my_arr_2[r] > sum)
r--;
else
l++;
}
System.out.print("두 배열에서 합이 목표 값에 가장 가까운 쌍은 [" + my_arr_1[result_l] + ", " + my_arr_2[result_r] + "] 입니다.");
}
public static void main(String args[]){
Demo my_ob = new Demo();
int my_arr_1[] = {11, 56, 78, 99};
int my_arr_2[] = {12, 33, 69, 87};
int arr_1_len = my_arr_1.length;
int arr_2_len = my_arr_2.length;
int val = 79;
my_ob.closest_pair(my_arr_1, my_arr_2, arr_1_len, arr_2_len, val);
}
}
실행 결과
두 배열에서 합이 목표 값에 가장 가까운 쌍은 [11, 69] 입니다.
코드 설명
Demo 클래스에는 closest_pair 메서드가 정의되어 있으며, 이 메서드는 두 배열을 순회하면서 두 원소의 합이 미리 지정된 목표 값에 가장 가까워지는 조합을 찾아냅니다. main 메서드에서는 Demo 클래스의 인스턴스를 생성하고 두 개의 배열을 정의한 뒤, 각 배열의 길이를 변수에 저장합니다. 이후 배열과 길이, 목표 값을 인수로 전달해 메서드를 호출하면 결과가 콘솔에 출력됩니다.
주의 사항
이 알고리즘은 두 배열이 오름차순으로 정렬되어 있다는 전제하에 동작합니다. 따라서 입력 배열이 정렬되어 있지 않다면 Arrays.sort() 등을 사용해 먼저 정렬한 후 메서드를 호출해야 올바른 결과를 얻을 수 있습니다.
시간 복잡도
포인터 l과 r이 각각 배열을 한 번씩만 지나가므로, 배열의 길이를 n과 m이라 할 때 시간 복잡도는 O(n + m)입니다. 모든 쌍을 확인하는 브루트 포스 방식의 O(n × m)보다 훨씬 효율적이며, 추가로 사용하는 메모리 역시 상수 수준(O(1))에 불과합니다.