이 글에서는 아래의 문제 설명에 대한 해결 방법을 단계별로 알아보겠습니다.
문제 설명 — 두 개의 정렬된 배열이 주어졌을 때, 두 배열에서 하나씩 선택한 요소의 합이 목표값 x에 가장 가까운 쌍(closest pair)을 찾아야 합니다.
이 문제는 투 포인터(Two Pointer) 기법을 활용하면 효율적으로 해결할 수 있습니다. 첫 번째 배열은 왼쪽 끝에서 시작하고, 두 번째 배열은 오른쪽 끝에서 시작하여 두 요소의 합과 목표값의 차이를 비교하면서 포인터를 이동시키는 방식입니다. 이 방법의 시간 복잡도는 O(m+n)으로, 모든 조합을 일일이 확인하는 브루트 포스 방식(O(m×n))보다 훨씬 빠릅니다.
예제 코드
# sys module
import sys
# pair
def print_(ar1, ar2, m, n, x):
# difference
diff = sys.maxsize
# index
l = 0
r = n - 1
while(l < m and r >= 0):
# closest pair
if abs(ar1[l] + ar2[r] - x) < diff:
res_l = l
res_r = r
diff = abs(ar1[l] + ar2[r] - x)
# pair sum
if ar1[l] + ar2[r] > x:
r = r - 1
else:
l = l + 1
# Print the result
print("The closest pair available is [", ar1[res_l], ",", ar2[res_r], "]")
# main
ar1 = [1, 3, 6, 9]
ar2 = [11, 23, 35, 50]
m = len(ar1)
n = len(ar2)
x = 20
print_(ar1, ar2, m, n, x)
출력 결과
The closest pair available is [ 9 , 11 ]
위 코드에서 사용된 변수들은 모두 지역 범위(local scope) 내에서 선언되며, 각 변수의 역할은 다음과 같습니다.
- diff : 현재까지 발견한 최소 차이를 저장하며, 초기값은 sys.maxsize로 설정됩니다.
- l, r : 첫 번째 배열의 시작 인덱스와 두 번째 배열의 마지막 인덱스를 가리키는 포인터입니다.
- res_l, res_r : 가장 가까운 쌍의 인덱스를 저장하는 변수입니다.
동작 원리
두 배열 요소의 합이 목표값 x보다 크면 오른쪽 포인터(r)를 감소시켜 합을 줄이고, x보다 작거나 같으면 왼쪽 포인터(l)를 증가시켜 합을 키웁니다. 이 과정을 반복하면서 합과 x의 차이가 최소가 되는 쌍을 계속 갱신하며, 두 포인터 중 하나가 범위를 벗어나면 탐색을 종료합니다.
예제에서는 ar1의 9와 ar2의 11을 더하면 20이 되어 목표값과 정확히 일치하므로, [9, 11]이 가장 가까운 쌍으로 출력됩니다.
결론
이 글에서는 Python을 사용하여 두 개의 정렬된 배열에서 목표값에 가장 가까운 쌍을 찾는 프로그램을 구현하는 방법을 살펴보았습니다. 투 포인터 기법을 활용하면 O(m+n)의 시간 복잡도로 문제를 효율적으로 해결할 수 있으며, 배열이 이미 정렬되어 있다는 조건만 있다면 대규모 데이터에서도 빠르게 동작합니다.