C++로 범위 내 누락된 숫자 하나 찾기

문제 개요

이 문제에서는 크기가 n인 배열 arr[]가 주어지며, 주어진 범위에서 누락된 숫자 하나를 찾는 것이 목표입니다.

배열은 최솟값부터 (최솟값 + n)까지의 모든 값으로 구성되어 있으며, 이 범위 중 단 하나의 요소만 배열에 빠져 있습니다. 우리가 해야 할 일은 바로 이 누락된 값을 찾아내는 것입니다.

예제를 통해 문제를 살펴보겠습니다.

입력

arr[] = {4, 8, 5, 7}

출력

위 예제에서 배열의 최솟값은 4이므로, 범위는 4부터 8까지가 됩니다. 이 범위의 값 {4, 5, 6, 7, 8} 중 배열에 존재하지 않는 숫자는 6 하나뿐입니다.

해결 접근 방법

1. 정렬 기반의 단순한 방법

가장 직관적인 해결 방법은 배열을 먼저 정렬한 뒤, 최솟값부터 시작하는 범위를 차례대로 확인하면서 배열에 없는 첫 번째 값을 찾는 것입니다.

이 방법은 구현이 간단하지만 정렬 과정이 필요하기 때문에 시간 복잡도가 O(n log n)으로, 큰 입력에서는 비효율적일 수 있습니다.

2. XOR 연산을 활용한 효율적인 방법

더 적은 시간 안에 문제를 해결하려면 XOR 연산을 활용할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

같은 값을 두 번 XOR하면 0이 됩니다 (x ^ x = 0)
0과 XOR하면 자기 자신이 유지됩니다 (x ^ 0 = x)

따라서 범위 내 모든 값의 XOR 결과와 배열 내 모든 값의 XOR 결과를 서로 XOR하면, 공통으로 존재하는 값들은 모두 사라지고 누락된 값만 남게 됩니다. 이 방법은 정렬이 필요 없으므로 O(n)의 시간 복잡도와 O(1)의 공간 복잡도로 문제를 해결할 수 있습니다.

예제 코드

다음 C++ 프로그램은 위 해결 방법의 동작을 보여줍니다.

#include <bits/stdc++.h>
using namespace std;
int findMissingNumArr(int arr[], int n){
    int arrMin = *min_element(arr, arr+n);
    int numXor = 0;
    int rangeXor = arrMin;
    for (int i = 0; i < n; i++) {
        numXor ^= arr[i];
        arrMin++;
        rangeXor ^= arrMin;
    }
    return numXor ^ rangeXor;
}
int main(){
    int arr[] = { 5, 7, 4, 8, 9};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"배열에서 누락된 값은 "<<findMissingNumArr(arr, n);
    return 0;
}

출력

배열에서 누락된 값은 6

코드 동작 원리

코드의 흐름을 단계별로 살펴보면 다음과 같습니다.

min_element() 함수로 배열의 최솟값을 구합니다. 이 값이 범위의 시작점이 됩니다.
반복문을 돌며 배열의 모든 요소를 numXor에 누적으로 XOR합니다.
동시에 최솟값부터 시작해 범위의 나머지 값들을 rangeXor에 누적으로 XOR합니다.
마지막에 두 XOR 값을 합치면 공통 값들은 상쇄되고 누락된 숫자만 반환됩니다.

이처럼 XOR 연산을 활용하면 추가 메모리나 정렬 없이 선형 시간 안에 누락된 숫자를 효율적으로 찾을 수 있습니다.