C++로 정렬된 배열에서 누락된 유일한 숫자 찾기

문제 개요

이 문제에서는 크기가 N인 배열 arr[]가 주어집니다. 배열에는 1부터 N까지의 값이 들어 있지만, 그중 단 하나의 값이 누락되어 있습니다. 우리의 목표는 정렬된 배열에서 누락된 그 유일한 숫자를 찾아내는 것입니다.

예시를 통해 문제를 이해해 보겠습니다.

입력

arr[] = {1, 2, 3, 5, 6, 7}

출력

접근 방법 1: 선형 탐색

가장 직관적인 해결 방법은 정렬된 배열을 처음부터 끝까지 선형으로 순회하는 것입니다. 배열이 오름차순으로 정렬되어 있고 1부터 N까지의 값 중 하나만 비어 있으므로, 인덱스와 값 사이에 arr[i] == (i + 1)이라는 규칙이 성립합니다. 이 규칙이 처음 깨지는 지점의 값, 즉 (i + 1)이 바로 누락된 숫자입니다.

예제 1

아래 프로그램은 이 해결 방법의 동작 과정을 보여줍니다.

#include <iostream>
using namespace std;
int findMissingValArray(int arr[], int N){
    for(int i = 0; i < N; i++){
        if(arr[i] != (i+1))
            return (i+1);
    }
    return -1;
}
int main(){
    int arr[] = {1, 2, 3, 4, 6};
    int N = sizeof(arr)/sizeof(arr[0]);
    cout<<"배열에서 누락된 값은 "<<findMissingValArray(arr, N);
    return 0;
}

출력

배열에서 누락된 값은 5

선형 탐색은 구현이 간단하지만 모든 요소를 한 번씩 확인해야 하므로 시간 복잡도는 O(N)입니다.

접근 방법 2: 이진 탐색

배열이 이미 정렬되어 있다는 점을 활용하면 이진 탐색(binary search)으로 더 효율적으로 문제를 풀 수 있습니다. mid 위치의 값을 검사하여 다음과 같이 판단합니다.

arr[mid] != mid + 1이면서 arr[mid - 1] == mid라면, 누락된 숫자는 바로 mid + 1입니다.
arr[mid] != mid + 1이라면 누락된 위치는 왼쪽 부분 배열에 있으므로 탐색 범위를 왼쪽으로 좁힙니다.
그 외의 경우에는 누락된 위치가 오른쪽 부분 배열에 있으므로 탐색 범위를 오른쪽으로 좁힙니다.

이 방식의 시간 복잡도는 O(log N)으로, 선형 탐색보다 훨씬 빠릅니다.

예제 2

아래 프로그램은 이진 탐색 기반 해결 방법의 동작 과정을 보여줍니다.

#include <iostream>
using namespace std;
int findMissingValArray(int arr[], int N){
    int s = 0, e = N - 1;
    while (s <= e) {
        int mid = (s + e) / 2;
        if (arr[mid] != mid + 1 && arr[mid - 1] == mid)
            return (mid + 1);
        if (arr[mid] != (mid + 1))
            e = (mid - 1);
        else
            s = (mid + 1);
    }
    return -1;
}
int main(){
    int arr[] = {1, 2, 3, 4, 6};
    int N = sizeof(arr)/sizeof(arr[0]);
    cout<<"배열에서 누락된 값은 "<<findMissingValArray(arr, N);
    return 0;
}

출력

배열에서 누락된 값은 5

마무리

정렬된 배열에서 누락된 숫자를 찾는 문제는 두 가지 방식으로 해결할 수 있습니다. 구현이 쉬운 선형 탐색(O(N))과, 정렬 특성을 활용해 성능을 끌어올린 이진 탐색(O(log N))이 그것입니다. 입력 배열이 정렬되어 있다는 조건이 주어진다면, 데이터 크기가 클수록 이진 탐색을 사용하는 것이 훨씬 유리합니다.