[BOJ] 17298. 오큰수

17298. 오큰수

1. 문제

크기가 N인 수열 $A$ = $A_1$, $A_2$, ..., $A_N$이 있다. 수열의 각 원소 $A_i$에 대해서 오큰수 NGE(i)를 구하려고 한다. $A_i$의 오큰수는 오른쪽에 있으면서 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이다.

2. 입력

첫째 줄에 수열 $A$의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 $A$의 원소 $A$ = $A_1$, $A_2$, ..., $A_N$ (1 ≤ $A_i$ ≤ 1,000,000)이 주어진다.

3. 출력

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

4. 풀이

C++

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

int N;
stack<int> A, s, ans;

void Solve()
{
    while (!A.empty())
    {
        if (s.empty()) ans.push(-1);
        else if (s.top() <= A.top())
        {
            while (!s.empty() && s.top() <= A.top()) s.pop();
            if (s.empty()) ans.push(-1);
            else ans.push(s.top());
        }
        else if (s.top() > A.top()) ans.push(s.top());
    
        s.push(A.top());
        A.pop();
    }
}


int main()
{
    cin >> N;
    int x;
    for (int i = 0; i < N; ++i)
    {
        cin >> x;
        A.push(x);
    }
    
    Solve();
    
    while (!ans.empty())
    {
        cout << ans.top() << ' ';
        ans.pop();
    }
}