C++에서 배열의 모든 요소에 대해 가장 가까운 큰 값 찾는 방법

이 글에서는 배열의 모든 요소에 대해 가장 가까운 '더 큰 값'을 찾는 방법을 살펴봅니다. 어떤 요소 x보다 크면서 배열 안에 실제로 존재하는 값이 있다면, 그 값이 해당 요소의 다음으로 큰 값(next greater value)이 됩니다. 만약 그런 값이 존재하지 않으면 -1을 반환합니다.

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

C++ STL의 set을 활용한 접근 방법

이 문제는 C++ STL의 set을 사용하면 효율적으로 해결할 수 있습니다. set은 이진 탐색 트리(레드-블랙 트리) 기반으로 구현되어 있으며, 이진 트리에서 중위 순회상의 후속자(in-order successor)는 항상 다음으로 큰 원소입니다. 따라서 upper_bound() 함수를 활용하면 O(log n) 시간 복잡도로 특정 요소보다 큰 값을 빠르게 찾을 수 있습니다.

동작 과정

1. 배열의 모든 요소를 set에 삽입하여 중복 없이 정렬된 상태로 관리합니다.
2. 각 요소에 대해 upper_bound()를 호출하여 해당 요소보다 큰 첫 번째 값을 찾습니다.
3. 결과가 end() 반복자와 같다면 더 큰 값이 존재하지 않는 것이므로 -1을 출력합니다.
4. 그렇지 않으면 찾아낸 값을 출력합니다.

예제 코드

#include<iostream>
#include<set>
using namespace std;

void nearestGreatest(int arr[], int n) {
    set<int> tempSet;
    // 배열의 모든 요소를 set에 삽입
    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), upper_bound() 호출에도 O(log n)이 소요되므로, 전체 시간 복잡도는 O(n log n)입니다. 공간 복잡도는 모든 요소를 저장하기 위한 set 때문에 O(n)입니다. 이 방법은 단순히 각 요소마다 배열 전체를 선형 탐색하는 O(n²) 방식보다 훨씬 효율적이라는 장점이 있습니다.