C++ STL set을 활용해 배열의 각 요소보다 큰 가장 가까운 값 찾기

이번 글에서는 배열의 모든 요소에 대해 자신보다 큰 값 중 가장 가까운 값을 찾는 방법을 알아보겠습니다. 어떤 요소 x보다 큰 값이 배열 안에 존재한다면 그 값을 결과로 출력하고, 존재하지 않는다면 -1을 반환합니다.

예를 들어 배열이 [10, 5, 11, 6, 20, 12]라면, 각 요소에 대한 결과는 [11, 6, 12, 10, -1, 20]이 됩니다. 여기서 20보다 큰 값은 배열에 없으므로 -1이 출력됩니다.

접근 방법: C++ STL의 set 활용

이 문제는 C++ STL의 set을 사용하면 효율적으로 해결할 수 있습니다. set은 내부적으로 이진 탐색 트리(Binary Search Tree) 구조로 구현되어 있으며, 트리에서 중위 순회(inorder) 기준 다음 노드가 항상 바로 다음으로 큰 값(inorder successor)이 됩니다. 따라서 upper_bound() 함수를 이용하면 특정 값보다 큰 원소 중 가장 작은 값을 O(log n) 시간에 찾을 수 있습니다.

알고리즘 단계

1. 배열의 모든 요소를 set에 삽입합니다.
2. 각 배열 요소에 대해 upper_bound()를 호출하여 자신보다 큰 첫 번째 값을 찾습니다.
3. 해당 값이 존재하면 출력하고, 존재하지 않으면(반환된 반복자가 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, 6, 20, 12};
    int n = sizeof(arr) / sizeof(arr[0]);
    nearestGreatest(arr, n);
}

실행 결과

11 6 12 10 -1 20

시간 복잡도 분석

set에 요소를 삽입하는 데 각각 O(log n)이 소요되므로 전체 삽입은 O(n log n)입니다. 또한 각 요소에 대해 upper_bound 연산 역시 O(log n)이므로, 전체 시간 복잡도는 O(n log n)입니다. 단순히 매번 배열을 순회하며 비교하는 O(n²) 방식보다 훨씬 효율적이라는 점이 이 방법의 핵심 장점입니다.