문제 상황
두 개의 리스트 nums1과 nums2가 있다고 가정해 보겠습니다. 이 두 리스트는 각각 센서 측정값을 나타내며, 모든 값은 고유합니다(즉, a ≠ b). 두 리스트 중 하나는 정확한 센서 측정값을 담고 있지만, 다른 하나에는 오류가 포함되어 있습니다.
오류가 있는 리스트에서는 마지막 값이 아닌 임의의 값 하나가 삭제되었고, 그 결과 잘못된 값이 리스트의 맨 끝에 추가되었습니다. 우리가 찾아야 하는 것은 바로 삭제된 실제 값입니다.
예를 들어 입력이 nums1 = [5, 10, 15], nums2 = [10, 15, 8]이라면 출력은 5가 됩니다. 첫 번째 리스트 nums1이 실제 값 [5, 10, 15]를 담고 있으며, 두 번째 배열에서는 5가 삭제된 뒤 8이 맨 끝에 삽입되었기 때문입니다.
해결 접근 방식: 이진 탐색
이 문제는 이진 탐색(Binary Search)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다. 값이 삭제된 지점까지는 두 리스트가 완전히 동일하지만, 그 지점부터는 한 칸씩 어긋나게 됩니다. 따라서 두 리스트가 처음으로 달라지는 위치를 찾으면, 그 위치가 곧 값이 삭제된 지점입니다.
알고리즘 단계
- low := 0, high := len(nums1) - 1로 초기화합니다.
- low < high인 동안 다음을 반복합니다:
- mid := (low + high) // 2 (중간 인덱스)
- 만약 nums1[mid] == nums2[mid]라면 → 삭제 지점은 뒤쪽에 있으므로 low := mid + 1
- 그렇지 않다면 → 삭제 지점은 현재 위치 또는 그 앞이므로 high := mid
- 반복이 종료되면, nums1[low + 1] == nums2[low]일 경우 nums1[low]를 반환하고, 그렇지 않으면 nums2[low]를 반환합니다.
Python 구현 예제
더 나은 이해를 위해 다음 구현 코드를 살펴보겠습니다.
def solve(nums1, nums2):
low, high = 0, len(nums1) - 1
while low < high:
mid = (low + high) // 2
if nums1[mid] == nums2[mid]:
low = mid + 1
else:
high = mid
return nums1[low] if nums1[low + 1] == nums2[low] else nums2[low]
nums1 = [5, 10, 15]
nums2 = [10, 15, 8]
print(solve(nums1, nums2))입력
[5, 10, 15], [10, 15, 8]
출력
5
복잡도 분석
- 시간 복잡도: O(log n) — 매 반복마다 탐색 범위가 절반으로 줄어들어 매우 효율적입니다.
- 공간 복잡도: O(1) — 별도의 추가 저장 공간 없이 포인터 변수만 사용합니다.