C++로 범위 내 누락된 요소 찾기: 3가지 효율적인 접근 방법

이 문제에서는 크기가 n인 배열 arr[]와 시작(start) 및 끝(end) 요소로 정의된 범위가 주어집니다. 우리의 목표는 주어진 범위 중 배열에 존재하지 않는 요소(누락된 요소)를 찾아 출력하는 것입니다.

문제 설명

범위 [start, end]에 속한 모든 숫자를 확인하고, 그중 배열에 포함되어 있지 않은 요소들을 찾아내는 것이 핵심입니다.

예제로 이해하기

입력

arr[] = {4, 6, 3, 7}, start = 3, end = 8

출력

5, 8

설명

• 전체 범위: [3, 4, 5, 6, 7, 8]
• 배열 요소: {4, 6, 3, 7}
• 범위에는 있지만 배열에는 없는 요소: 5, 8

접근 방법 1: 정렬과 lower_bound 활용

가장 직관적인 방법은 배열을 먼저 오름차순으로 정렬한 뒤, 범위의 첫 번째 값(low)이 배열에서 처음 나타나는 위치를 lower_bound() 함수로 찾는 것입니다. 이후 해당 위치부터 배열과 범위 값을 하나씩 비교하며 일치하지 않는 값을 출력합니다. 범위 끝(high)까지 비교가 완료되지 않았다면 남은 값들도 모두 출력합니다.

구현 예제

#include <bits/stdc++.h>
using namespace std;

void findMissingElements(int arr[], int n, int low, int high){
    sort(arr, arr + n);
    int* pointerVal = lower_bound(arr, arr + n, low);
    int index = pointerVal - arr;
    int i = index, x = low;
    while (i < n && x <= high) {
        if (arr[i] != x)
            cout << x << " ";
        else
            i++;
        x++;
    }
    while (x <= high)
        cout<<x++<<" ";
}

int main(){
    int arr[] = { 4, 6, 3, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int low = 3, high = 9;
    cout<<"누락된 요소: ";
    findMissingElements(arr, n, low, high);
    return 0;
}

출력 결과

누락된 요소: 5 8 9

정렬에 O(n log n), 탐색에 O(n)의 시간이 소요되므로 전체 시간 복잡도는 O(n log n)입니다.

접근 방법 2: 불리언(Boolean) 배열 활용

두 번째 방법은 크기가 (end - start + 1)인 불리언 배열을 생성하는 것입니다. 원본 배열의 각 요소가 범위 내에 있다면, 불리언 배열의 해당 인덱스(i + start 위치)를 true로 표시합니다. 마지막으로 불리언 배열을 순회하면서 false로 남아 있는 값, 즉 누락된 요소들을 출력합니다.

구현 예제

#include <bits/stdc++.h>
using namespace std;

void findMissingElements(int arr[], int n, int start, int end){
    bool boolArray[end - start + 1] = { false };
    for (int i = 0; i < n; i++) {
        if (start <= arr[i] && arr[i] <= end)
            boolArray[arr[i] - start] = true;
    }
    for (int i = 0; i <= end - start; i++) {
        if (boolArray[i] == false)
            cout<<(start + i)<<"\t";
    }
}

int main(){
    int arr[] = { 4, 6, 3, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int low = 3, high = 9;
    cout<<"누락된 요소: ";
    findMissingElements(arr, n, low, high);
    return 0;
}

출력 결과

누락된 요소: 5 8 9

이 방법은 정렬이 필요 없으며 시간 복잡도가 O(n + m)(m은 범위의 크기)으로 매우 효율적입니다. 다만 범위가 매우 클 경우 불리언 배열이 차지하는 메모리를 고려해야 합니다.

접근 방법 3: 해시 테이블(HashSet) 활용

세 번째 방법은 해시 테이블을 사용하는 것입니다. 배열의 모든 요소를 unordered_set에 삽입한 후, 범위의 각 값을 순회하며 집합에 존재하지 않는 값만 출력합니다. 해시 기반 자료구조 덕분에 존재 여부 확인이 평균 O(1)에 이루어집니다.

구현 예제

#include <bits/stdc++.h>
using namespace std;

void findMissingElements(int arr[], int n, int start, int end){
    unordered_set<int> arrEle;
    for (int i = 0; i < n; i++)
        arrEle.insert(arr[i]);
    for (int i = start; i <= end; i++)
        if (arrEle.find(i) == arrEle.end())
            cout<<i<<"\t";
}

int main(){
    int arr[] = { 4, 6, 3, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int low = 3, high = 9;
    cout<<"누락된 요소: ";
    findMissingElements(arr, n, low, high);
    return 0;
}

출력 결과

누락된 요소: 5 8 9

시간 복잡도는 O(n + m)이며, 공간 복잡도는 O(n)입니다. 정렬 없이 빠른 조회가 가능하다는 점이 장점입니다.

마무리 및 방법 비교

세 가지 방법 모두 동일한 결과를 출력하지만, 입력 크기와 범위의 크기, 메모리 제약 조건에 따라 적합한 방법이 달라집니다. 범위가 좁다면 불리언 배열 방식이, 추가 메모리 사용을 피하고 싶다면 정렬 기반 방식이, 일반적인 경우에는 해시 테이블 방식이 좋은 선택이 될 수 있습니다.