C++로 구현하는 다음 큰 요소(Next Greater Element) 알고리즘

다음 큰 요소(Next Greater Element)란 특정 요소 뒤에서 처음으로 등장하는, 그 요소보다 큰 값을 가진 요소를 의미합니다. 만약 뒤쪽에 더 큰 요소가 존재하지 않는다면 -1로 표시합니다.

간단한 예시를 통해 살펴보겠습니다.

arr = [4, 5, 3, 2, 1]

4의 다음 큰 요소는 5입니다.
3, 2, 1의 경우 뒤에 더 큰 요소가 없으므로 -1이 됩니다.

알고리즘 개요

이 문제는 스택(Stack) 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 알고리즘의 진행 순서는 다음과 같습니다.

배열을 임의의 숫자들로 초기화합니다.
스택을 하나 생성하고, 배열의 첫 번째 요소를 스택에 push 합니다.
배열의 두 번째 요소부터 마지막 요소까지 순회(iterate)합니다.
- 스택이 비어 있다면 현재 요소를 스택에 push 하고 다음 요소로 넘어갑니다.
- 현재 요소가 스택의 최상단(top) 요소보다 큰 동안 반복합니다.
  - 스택의 top 요소를 출력하되, 그 다음 큰 요소를 현재 요소로 지정합니다.
  - top 요소를 pop 하여 제거합니다.
- 현재 요소를 스택에 push 합니다.
모든 요소를 순회한 후에도 스택에 남아 있는 요소들은 뒤에 더 큰 요소가 없는 것이므로, 각각 -1을 다음 큰 요소로 하여 출력합니다.

C++ 구현 코드

위에서 설명한 알고리즘을 C++로 구현한 코드는 다음과 같습니다.

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

void nextGreaterElements(int arr[], int n) {
    stack<int> s;
    s.push(arr[0]);

    for (int i = 1; i < n; i++) {
        // 스택이 비어 있으면 현재 요소를 push
        if (s.empty()) {
            s.push(arr[i]);
            continue;
        }

        // 현재 요소가 스택의 top보다 클 때까지 반복
        while (!s.empty() && s.top() < arr[i]) {
            cout << s.top() << " -> " << arr[i] << endl;
            s.pop();
        }

        s.push(arr[i]);
    }

    // 스택에 남은 요소들의 다음 큰 요소는 -1
    while (!s.empty()) {
        cout << s.top() << " -> " << -1 << endl;
        s.pop();
    }
}

int main() {
    int arr[] = { 1, 2, 3, 4, 5 };
    int n = 5;

    nextGreaterElements(arr, n);

    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

1 -> 2
2 -> 3
3 -> 4
4 -> 5
5 -> -1

복잡도 분석

시간 복잡도: O(n) — 각 요소는 최대 한 번 push 되고 한 번 pop 되므로, 전체 연산 횟수는 배열의 크기에 비례합니다.
공간 복잡도: O(n) — 최악의 경우(내림차순 정렬된 배열) 모든 요소가 스택에 저장될 수 있습니다.

이처럼 스택을 활용하면 이중 반복문을 사용하는 단순한 방식(O(n²))보다 훨씬 효율적으로 다음 큰 요소 문제를 해결할 수 있습니다.