[C++ / Algorithm] 백준 17298번 오큰수 #20

1. 오큰수

1-1. 문제

크기가 N인 수열 A = A1, A2, …, AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다.
Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다.
그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다.
A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

1-2. 입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, …, AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

2. 풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

int main() {
    int seriesLength;
    vector<int> series;
    stack<int> results;

    cin >> seriesLength;

    series.begin();

    for (int n = 0; n < seriesLength; n++) {
        int element;

        cin >> element;

        series.push_back(element);
    }

    for (int index = 0; index < series.size(); index++) {

        while (true) {
            if (results.empty()) {
                results.push(index);
                break;
            }
            int topIndex = results.top();

            if (series[topIndex] >= series[index]) {
                results.push(index);
                break;
            }
            else {
                results.pop();
                series[topIndex] = series[index];
            }
        }
    }

    while (!results.empty()) {
        series[results.top()] = -1;
        results.pop();
    }

    for (auto element : series) {
        cout << element << " ";
    }
}

22
2 6 1 7 9 4 1 3 4 6 8 5 3 6 2 4 8 2 1 3 7 8

6 7 7 9 -1 6 3 4 6 8 -1 6 6 8 4 8 -1 3 3 7 8 -1