개념
n개의 서로 다른 정수로 이루어진 배열 array[]가 주어집니다. 요소들은 오름차순으로 연속적으로 배치되어 있지만, 그중 하나의 요소가 빠져 있습니다. 우리의 목표는 이진 탐색(Binary Search)을 활용해 O(logN) 시간 안에 누락된 요소를 찾아내는 것입니다.
입력 및 출력 예시
예시 1
array[] = {1, 2, 3, 4, 5, 6, 7, 9}
출력: 8
예시 2
array[] = {-4, -2, -1, 0, 1, 2}
출력: -3
예시 3
array[] = {1, 2, 3, 4}
출력: -1
세 번째 예시처럼 누락된 요소가 없다면 -1을 반환합니다.
접근 방법
핵심 원리: 불일치(Inconsistency) 판별
배열이 연속적이라면, 모든 요소에 대해 '요소 값과 해당 인덱스의 차이'는 항상 첫 번째 요소인 array[0]과 같아야 한다는 규칙이 성립합니다.
예시:
A[] = {1, 2, 3, 4, 5} → 일관됨 (Consistent)
B[] = {201, 202, 203, 204} → 일관됨 (Consistent)
C[] = {1, 2, 3, 5, 6} → 불일치 (Inconsistent): C[3] − 3 ≠ C[0], 즉 5 − 3 ≠ 1
이 불일치 여부를 판별하면 매 탐색마다 배열의 절반만 확인하면 되므로, 선형 탐색(O(N)) 대신 O(logN)의 시간 복잡도로 문제를 해결할 수 있습니다.
알고리즘 단계
중간(mid) 요소를 구하고, 해당 요소가 일관적인지 확인합니다.
중간 요소가 일관된 경우: 중간 요소와 다음 요소의 차이가 1보다 큰지 확인합니다 (
array[mid + 1] − array[mid] > 1).
- 조건이 참이면array[mid] + 1이 누락된 요소입니다.
- 아니라면 중간 기준 오른쪽 절반을 탐색 범위로 삼고 1단계로 돌아갑니다.중간 요소가 불일치하는 경우: 중간 요소와 이전 요소의 차이가 1보다 큰지 확인합니다 (
array[mid] − array[mid − 1] > 1).
- 조건이 참이면array[mid] − 1이 누락된 요소입니다.
- 아니라면 중간 기준 왼쪽 절반을 탐색 범위로 삼고 1단계로 돌아갑니다.
C++ 구현 예제
// C++ 구현 예제
#include<bits/stdc++.h>
using namespace std;
// 누락된 요소를 반환하는 함수
int findMissing(int array[], int n1){
int low = 0, high = n1 - 1;
int mid1;
while (high > low){
mid1 = low + (high - low) / 2;
// 중간 요소의 일관성 확인
if (array[mid1] - mid1 == array[0]){
// 중간 지점까지는 불일치 없음
// 누락된 요소가 중간 요소 바로 뒤에 있는 경우
if (array[mid1 + 1] - array[mid1] > 1)
return array[mid1] + 1;
else{
// 오른쪽 절반으로 이동
low = mid1 + 1;
}
}
else{
// 불일치 발견
// 누락된 요소가 중간 요소 바로 앞에 있는 경우
if (array[mid1] - array[mid1 - 1] > 1)
return array[mid1] - 1;
else{
// 왼쪽 절반으로 이동
high = mid1 - 1;
}
}
}
// 누락된 요소를 찾지 못한 경우
return -1;
}
// 드라이버 코드
int main(){
int array[] = { -9, -8, -6, -5, -4, -3, -2, -1, 0 };
int n1 = sizeof(array)/sizeof(array[0]);
cout << "The Missing Element:" <<(findMissing(array, n1));
}
실행 결과
The Missing Element:-7
복잡도 분석
시간 복잡도: O(logN) — 매 반복마다 탐색 범위가 절반으로 줄어듭니다.
공간 복잡도: O(1) — 추가 메모리 없이 포인터(low, high)만 사용합니다.