문제 개요
정렬된 배열 A가 주어졌다고 가정해 봅시다. 이 배열의 모든 요소는 두 번씩 나타나지만, 단 하나의 요소만 한 번만 등장합니다. 우리의 목표는 바로 이 고유한 요소를 찾아내는 것입니다.
예를 들어 배열이 [1, 1, 3, 3, 4, 4, 5, 6, 6, 7, 7, 9, 9]라면, 한 번만 나타나는 요소는 5입니다.
접근 방법: 이진 탐색
배열이 정렬되어 있고 각 요소가 쌍을 이루고 있다는 특성을 활용하면, 선형 탐색(O(n)) 대신 이진 탐색(O(log n))으로 문제를 훨씬 효율적으로 해결할 수 있습니다.
핵심 아이디어
고유한 요소를 기준으로 배열의 인덱스 패턴이 달라진다는 점이 핵심입니다.
- 고유 요소 이전 구간: 첫 번째 발생은 짝수 인덱스(0, 2, 4, …)에, 두 번째 발생은 홀수 인덱스(1, 3, 5, …)에 위치합니다.
- 고유 요소 이후 구간: 패턴이 뒤바뀌어 첫 번째 발생은 홀수 인덱스에, 두 번째 발생은 짝수 인덱스에 위치합니다.
따라서 중간 인덱스 mid를 구한 뒤 다음과 같이 판단합니다.
mid가 짝수인 경우:A[mid]와A[mid + 1]을 비교하여 두 값이 같으면 고유 요소는 오른쪽에 있으므로 오른쪽 구간을 탐색하고, 다르면 왼쪽 구간을 탐색합니다.mid가 홀수인 경우:A[mid]와A[mid - 1]을 비교하여 두 값이 같으면 오른쪽 구간을, 다르면 왼쪽 구간을 탐색합니다.
이 과정을 재귀적으로 반복하면 탐색 범위가 계속 절반으로 줄어들어, 최종적으로 고유한 요소를 O(log n) 시간 안에 찾을 수 있습니다.
C++ 구현 예제
#include<iostream>
using namespace std;
void findSingleElement(int *arr, int left, int right) {
// 탐색 범위가 유효하지 않으면 종료
if (left > right)
return;
// 범위에 요소가 하나만 남았다면 그것이 고유한 요소
if (left == right) {
cout << "찾는 요소는: " << arr[left];
return;
}
int mid = (left + right) / 2;
if (mid % 2 == 0) {
// mid가 짝수인 경우: 오른쪽 요소와 비교
if (arr[mid] == arr[mid + 1])
findSingleElement(arr, mid + 2, right);
else
findSingleElement(arr, left, mid);
} else {
// mid가 홀수인 경우: 왼쪽 요소와 비교
if (arr[mid] == arr[mid - 1])
findSingleElement(arr, mid + 1, right);
else
findSingleElement(arr, left, mid - 1);
}
}
int main() {
int arr[] = {1, 1, 3, 3, 4, 4, 5, 6, 6, 7, 7, 9, 9};
int len = sizeof(arr) / sizeof(arr[0]);
findSingleElement(arr, 0, len - 1);
}실행 결과
찾는 요소는: 5
복잡도 분석
- 시간 복잡도: O(log n) — 매 단계마다 탐색 범위가 절반으로 줄어듭니다.
- 공간 복잡도: O(log n) — 재귀 호출 스택이 사용됩니다. 반복문으로 변환하면 O(1)로 줄일 수 있습니다.
이처럼 정렬된 배열에서 쌍을 이루지 않는 유일한 요소는 이진 탐색을 활용하면 매우 효율적으로 찾을 수 있습니다.