이 튜토리얼에서는 주어진 정렬되지 않은 배열에서 k번째 누락된 요소를 찾는 프로그램을 작성해 보겠습니다.
즉, 배열의 최솟값(min)부터 최댓값(max) 사이에 존재하지 않는 숫자들 중에서 k번째에 해당하는 값을 찾는 것이 목표입니다. 그럼 문제를 해결하는 단계를 하나씩 살펴보겠습니다.
문제 해결 접근 방식
- 정렬되지 않은 배열을 초기화합니다.
- 빠른 탐색을 위해 모든 배열 요소를
unordered_set에 삽입합니다. - 배열에서 최댓값과 최솟값을 구합니다.
- 최솟값부터 최댓값까지 반복하는 루프를 작성하고, 누락된 개수를 세기 위한 변수(count)를 유지합니다.
- 현재 값이 집합(set)에 존재하지 않으면 count를 1 증가시킵니다.
- count가 k와 같아지면 해당 값 i를 반환합니다.
만약 범위 내에서 누락된 숫자의 개수가 k보다 적다면, 조건을 만족하는 값이 없다는 의미로 -1을 반환하도록 처리합니다.
C++ 코드 예제
실제 동작하는 전체 코드를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int findMissingNumber(int arr[], int n, int k) {
unordered_set<int> numbers;
int count = 0;
for (int i = 0; i < n; i++) {
numbers.insert(arr[i]);
}
int max = *max_element(arr, arr + n);
int min = *min_element(arr, arr + n);
for (int i = min + 1; i < max; i++) {
if (numbers.find(i) == numbers.end()) {
count++;
}
if (count == k) {
return i;
}
}
return -1;
}
int main() {
int arr[] = { 1, 10, 3, 2, 5 }, n = 5;
int k = 3;
cout << findMissingNumber(arr, n, k) << endl;
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
7
결과 분석
예제 배열은 {1, 10, 3, 2, 5}이므로 최솟값은 1, 최댓값은 10입니다. 이 범위 안에서 빠져 있는 숫자들을 차례대로 나열하면 다음과 같습니다.
4 → 6 → 7 → 8 → 9
여기서 세 번째(k = 3)로 누락된 숫자는 7이므로 프로그램은 7을 출력하게 됩니다.
복잡도 분석
- 시간 복잡도: 배열 요소를 집합에 삽입하는 데 O(n), 최솟값~최댓값 구간을 순회하는 데 O(max − min)이 소요됩니다.
- 공간 복잡도: 모든 요소를 저장하는 집합 때문에 O(n)의 추가 공간이 필요합니다.
마무리
지금까지 C++의 unordered_set을 활용하여 정렬되지 않은 배열에서 k번째 누락된 요소를 찾는 방법을 알아보았습니다. 튜토리얼에 대해 궁금한 점이나 추가 질문이 있다면 댓글로 남겨주세요.