두 개의 리스트 L1과 L2가 주어졌을 때, L1의 어떤 숫자와 L2의 어떤 숫자 사이의 차이 중 가장 작은 값을 찾아야 한다고 가정해 봅시다.
예를 들어 입력이 L1 = [2, 7, 4], L2 = [16, 10, 11]이라면, 출력은 3이 됩니다. 가장 작은 차이가 10 - 7 = 3이기 때문입니다.
문제 해결 접근 방법
이 문제는 투 포인터(Two Pointer) 기법을 활용하면 효율적으로 해결할 수 있습니다. 두 리스트를 모두 정렬한 후, 각 리스트를 가리키는 포인터를 하나씩 두고 비교해 나가는 방식입니다. 단계별로 살펴보면 다음과 같습니다.
- 리스트 L1과 L2를 각각 정렬합니다.
- 정답 변수 ans를 무한대(infinity)로 초기화합니다.
- 포인터 i와 j를 각각 0으로 설정합니다.
- i가 L1의 크기보다 작고, j가 L2의 크기보다 작은 동안 다음을 반복합니다.
- ans를 'ans'와 '|L1[i] - L2[j]|' 중 더 작은 값으로 갱신합니다.
- L1[i]가 L2[j]보다 작으면 i를 1 증가시킵니다.
- 그렇지 않으면 j를 1 증가시킵니다.
- 반복이 끝나면 ans를 반환합니다.
동작 원리
두 리스트를 정렬하면 값들이 오름차순으로 배열되므로, 현재 비교 중인 두 값의 차이가 최솟값이 될 가능성이 높습니다. 만약 L1의 현재 값이 L2의 현재 값보다 작다면, L1의 값을 키워야 차이가 줄어들 수 있으므로 i를 앞으로 이동시키고, 반대의 경우에는 j를 이동시킵니다. 이 과정을 통해 O(N log N) 시간(정렬 비용 포함) 안에 최소 차이를 구할 수 있습니다.
구현 예제
class Solution:
def solve(self, L1, L2):
L1.sort()
L2.sort()
ans = float("inf")
i = j = 0
while i < len(L1) and j < len(L2):
ans = min(ans, abs(L1[i] - L2[j]))
if L1[i] < L2[j]:
i += 1
else:
j += 1
return ans
ob = Solution()
L1 = [2, 7, 4]
L2 = [16, 10, 11]
print(ob.solve(L1, L2))
입력
[2, 7, 4], [16, 10, 11]
출력
3
마무리
이처럼 두 리스트를 정렬한 뒤 투 포인터로 순회하는 방식은 단순한 완전 탐색(O(N×M))보다 훨씬 효율적입니다. 실무에서도 두 데이터 집합 간 가장 유사한 값을 빠르게 매칭해야 하는 상황에서 널리 활용되는 패턴이므로, 원리를 잘 익혀두면 다양한 알고리즘 문제에 응용할 수 있습니다.