C++로 정렬되지 않은 정수 배열에서 누락된 양수 찾기

정렬되지 않은 정수로 구성된 배열이 하나 주어져 있다고 가정해 보겠습니다. 우리가 해결해야 할 과제는 이 배열에서 [0부터 n] 범위 안의 숫자 중 실제로 존재하지 않는 양의 정수, 즉 '누락된 숫자'를 찾아내는 것입니다.

예시로 이해하기

입력-1

N = 9
arr = [0, 2, 5, 9, 1, 7, 4, 3, 6]

출력

설명 − 주어진 정렬되지 않은 배열에는 0부터 9까지의 숫자 중 '8'만 빠져 있으므로, 출력값은 8이 됩니다.

입력-2

N = 1
arr = [0]

출력

설명 − 크기가 1인 배열 [0]에는 0만 존재하므로, [0부터 1] 범위에서 누락된 양의 정수는 '1'입니다.

문제 해결 접근 방법

이 문제는 여러 가지 방식으로 접근할 수 있지만, 선형 시간 O(n)과 상수 공간 O(1)만으로도 매우 효율적으로 해결할 수 있습니다.

핵심 아이디어는 배열의 크기가 n이고 원소들이 [0부터 n] 범위에 속한다는 점을 활용하는 것입니다. 모든 배열 원소와 각 인덱스, 그리고 n 자체를 XOR 연산하면, 짝을 이루지 못한 단 하나의 값, 즉 누락된 숫자만 최종 결과로 남게 됩니다. 이는 XOR 연산이 동일한 값을 두 번 연산하면 서로 상쇄되어 0이 되는 성질을 가지고 있기 때문입니다.

원소들이 [0부터 n] 범위에 있는, 크기 N의 배열을 입력받습니다.
배열과 그 크기를 입력으로 받아 누락된 숫자를 반환하는 함수 findMissingNumber(int arr[], int size)를 정의합니다.
XOR 연산을 수행할 변수 n을 초기화하며, 초기값은 배열의 크기(size)로 설정합니다.
모든 배열 원소를 순회하면서 각 원소와 해당 인덱스를 누락 숫자 변수와 계속해서 XOR 연산합니다.
순회가 끝난 후 변수에 남아 있는 값이 곧 누락된 숫자이므로 이를 반환합니다.

C++ 구현 예제

#include<bits/stdc++.h>
using namespace std;
int findMissingNumber(int *arr, int size){
    int missing_no = size;
    for(int i = 0; i < size; i++){
        missing_no ^= i ^ arr[i];
    }
    return missing_no;
}
int main(){
    int n = 6;
    int arr[n] = {0, 4, 2, 1, 6, 3};
    cout<<findMissingNumber(arr, n)<<endl;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

배열 {0, 4, 2, 1, 6, 3}의 각 원소와 인덱스, 그리고 초기값 n=6을 모두 XOR 연산하면 짝이 맞는 값들은 모두 상쇄되고, 배열에 없는 유일한 값인 '5'만 최종 결과로 남게 됩니다.