오름차순으로 정렬된 서로 다른 n개의 숫자로 이루어진 배열 A가 있다고 가정해 보겠습니다. 이 배열에는 요소 하나가 빠져 있으며, 우리의 목표는 바로 그 누락된 요소를 찾아내는 것입니다.
예를 들어 입력이 A = [1, 2, 3, 4, 5, 6, 7, 9]라면, 1부터 9까지 연속된 숫자 중 8이 빠져 있으므로 출력 결과는 8이 됩니다.
접근 방법: 이진 탐색
배열이 이미 정렬되어 있기 때문에 이진 탐색(Binary Search)을 활용하면 선형 탐색보다 훨씬 효율적으로 문제를 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
누락된 요소가 없는 구간에서는 항상 A[i] - i == A[0]가 성립합니다. 즉, 각 요소 값과 해당 인덱스의 차이가 일정하게 유지됩니다. 만약 어느 지점에서 이 차이가 깨진다면, 그 지점 근처에 누락된 요소가 존재한다는 뜻입니다.
알고리즘 단계
- n := 배열 A의 크기
- left := 0, right := n - 1, mid := 0으로 초기화
- right > left인 동안 아래 과정을 반복합니다.
- mid := left + (right - left) / 2
- 만약 A[mid] - mid == A[0]이라면 (왼쪽 구간은 정상):
- A[mid + 1] - A[mid] > 1이면 A[mid] + 1을 반환합니다. (누락된 요소 발견)
- 그렇지 않으면 left := mid + 1로 설정하여 오른쪽 구간을 탐색합니다.
- 그렇지 않다면 (왼쪽 구간에 누락 존재):
- A[mid] - A[mid - 1] > 1이면 A[mid] - 1을 반환합니다.
- 그렇지 않으면 right := mid - 1로 설정하여 왼쪽 구간을 탐색합니다.
- 반복문이 종료되면 -1을 반환합니다. (누락된 요소가 없음)
구현 예시
아래 예제 코드를 통해 더 자세히 이해해 보겠습니다.
def search_missing_item(A):
n = len(A)
left, right = 0, n - 1
mid = 0
while (right > left):
mid = left + (right - left) // 2
if (A[mid] - mid == A[0]):
if (A[mid + 1] - A[mid] > 1):
return A[mid] + 1
else:
left = mid + 1
else:
if (A[mid] - A[mid - 1] > 1):
return A[mid] - 1
else:
right = mid - 1
return -1
A = [1, 2, 3, 4, 5, 6, 7, 9]
print(search_missing_item(A))입력
[1, 2, 3, 4, 5, 6, 7, 9]
출력
8
복잡도 분석
시간 복잡도: O(log n) — 매 반복마다 탐색 범위가 절반으로 줄어들기 때문에 매우 효율적입니다.
공간 복잡도: O(1) — 추가적인 메모리를 거의 사용하지 않습니다.
참고: 대안적인 방법
배열의 크기가 작다면 간단한 방법도 사용할 수 있습니다. 예를 들어 등차수열 합 공식을 이용해 기대값과 실제 합의 차이를 계산하거나, 인접한 두 요소를 순회하며 차이가 1보다 큰 지점을 찾는 O(n) 선형 탐색 방법도 있습니다. 하지만 배열이 정렬되어 있다는 조건이 주어졌다면, 위에서 소개한 이진 탐색 방식이 가장 효율적인 선택입니다.