[백준 c++] 17298 오큰수

문제 설명

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

아이디어

수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이라서 이중 for문으로 풀 수 없다.
그래서 재귀로 풀어야하나 했는데 최적의 경우의 수를 구하는 그리디를 생각했어야 했다. 그 중에서도 stack을 이용해서 풀 수 있었다.

stack.top()의 값보다 큰 값이 나오면 pop을 하고 아니면 값을 쌓는 식이다. 여기서 중요한건 출력이 입력 순서를 따라야 하기 때문에 스택에 넣는 값은 수열의 index다!

전체 코드

#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
int n, m;
int res[1000001], a[1000001];
stack<int> st;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        while (st.size() && a[st.top()] < a[i])
        {
            res[st.top()] = a[i];
            st.pop();
        }
        st.push(i);
    }
    for (int i = 0; i < n; i++)
    {
        int c = res[i];
        if (!c)
            c = -1;
        cout << c << " ";
    }
}