등차수열(Arithmetic Progression)의 원소들이 순서대로 담긴 배열이 있다고 가정해 봅시다. 이 배열에는 한 개의 원소가 누락되어 있으며, 우리의 목표는 바로 그 빠진 원소를 찾아내는 것입니다. 예를 들어 arr = [2, 4, 8, 10, 12, 14]와 같은 배열이 주어졌다면, 공차가 2인 등차수열에서 6이 빠져 있으므로 출력값은 6이 되어야 합니다.
이진 탐색을 활용한 접근 방법
이 문제는 이진 탐색(Binary Search)을 활용하면 O(log n)의 시간 복잡도로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 배열의 중간 요소(mid)를 선택합니다.
- 중간 요소와 그 다음 요소 사이의 차이가 공차(diff)와 일치하는지 검사합니다. 일치하지 않는다면, 누락된 숫자는 mid와 mid + 1 인덱스 사이에 존재하므로 즉시 반환할 수 있습니다.
- 중간 요소가 등차수열에서 n/2번째 위치에 해당한다면(즉, arr[mid] == arr[0] + mid * diff), 누락된 숫자는 오른쪽 절반에 있는 것이고,
- 그렇지 않다면 왼쪽 절반에서 탐색을 계속 진행합니다.
C++ 구현 예제
#include <iostream>
using namespace std;
#define INT_MAX 999999
class Progression {
public:
int missingUtil(int arr[], int left, int right, int diff) {
if (right <= left)
return INT_MAX;
int mid = left + (right - left) / 2;
if (arr[mid + 1] - arr[mid] != diff)
return (arr[mid] + diff);
if (mid > 0 && arr[mid] - arr[mid - 1] != diff)
return (arr[mid - 1] + diff);
if (arr[mid] == arr[0] + mid * diff)
return missingUtil(arr, mid + 1, right, diff);
return missingUtil(arr, left, mid - 1, diff);
}
int missingElement(int arr[], int n) {
int diff = (arr[n - 1] - arr[0]) / n;
return missingUtil(arr, 0, n - 1, diff);
}
};
int main() {
Progression pg;
int arr[] = {2, 4, 8, 10, 12, 14};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "The missing element is: " << pg.missingElement(arr, n)<<endl;
}입력
[2,4,8,10,12,14]
출력
The missing element is: 6
동작 원리 상세 설명
1. 공차 계산
diff = (마지막 원소 − 첫 번째 원소) / n으로 공차를 계산합니다. 누락된 원소가 하나 있기 때문에 실제 항의 개수보다 하나 많은 값인 n으로 나누어야 올바른 공차를 얻을 수 있습니다.
2. 누락 위치 판별
각 재귀 단계에서 현재 위치의 실제 값과 이론상 값(arr[0] + mid × diff)을 비교합니다. 두 값이 일치하면 앞부분은 온전하다는 뜻이므로 오른쪽 절반을, 일치하지 않으면 왼쪽 절반을 탐색 대상으로 삼습니다. 또한 인접한 두 요소의 차이를 검사하여 누락 지점을 정확히 특정할 수도 있습니다.
3. 시간 복잡도
매 단계마다 탐색 범위가 절반으로 줄어들기 때문에 전체 시간 복잡도는 O(log n)입니다. 선형 탐색(O(n)) 방식에 비해 배열이 클수록 성능 차이가 크게 벌어집니다.