이 글에서는 배열의 각 요소에 대해 그보다 크면서 가장 가까운 값을 찾는 방법을 알아봅니다. 어떤 요소 x보다 큰 값이 배열 안에 존재한다면, 그중 가장 작은 값(즉, x 바로 위의 값)이 x의 '가장 가까운 큰 값'이 됩니다. 만약 x보다 큰 값이 배열에 없다면 -1을 출력합니다.
예를 들어 배열이 [10, 5, 11, 10, 20, 12]라면 결과는 [11, 10, 12, 11, -1, 20]이 됩니다. 20보다 큰 값은 배열에 존재하지 않으므로 -1이 출력됩니다.
접근 방법
이 문제는 C++ STL의 set을 이용해 효율적으로 해결할 수 있습니다. set은 내부적으로 균형 이진 탐색 트리로 구현되어 있으며, 이진 탐색 트리에서 중위 순회(inorder traversal)상의 후계자(successor)는 항상 현재 값보다 큰 다음 원소입니다. 따라서 upper_bound() 함수를 활용하면 각 요소보다 큰 값 중 최솟값을 O(log n) 시간에 찾을 수 있습니다.
알고리즘 단계
- 배열의 모든 요소를 set에 삽입합니다.
- 각 요소에 대해 upper_bound()를 호출하여 해당 값보다 큰 첫 번째 원소를 찾습니다.
- 반환된 반복자가 end()라면 더 큰 값이 없다는 의미이므로 -1을 출력하고, 그렇지 않으면 해당 값을 출력합니다.
예제 코드
#include<iostream>
#include<set>
using namespace std;
void nearestGreatest(int arr[], int n) {
set<int> tempSet;
for (int i = 0; i < n; i++)
tempSet.insert(arr[i]);
for (int i = 0; i < n; i++) {
auto next_greater = tempSet.upper_bound(arr[i]);
if (next_greater == tempSet.end())
cout << -1 << " ";
else
cout << *next_greater << " ";
}
}
int main() {
int arr[] = {10, 5, 11, 10, 20, 12};
int n = sizeof(arr) / sizeof(arr[0]);
nearestGreatest(arr, n);
}출력 결과
11 10 12 11 -1 20
복잡도 분석
n개의 요소 각각에 대해 O(log n)의 탐색을 수행하므로 전체 시간 복잡도는 O(n log n)입니다. 또한 set에 모든 요소를 저장해야 하므로 공간 복잡도는 O(n)입니다.