17298번 오큰수

https://www.acmicpc.net/problem/17298

Next Greater Element(NGE) 알고리즘 : https://hsdevelopment.tistory.com/373

map을 활용해 각 원소의 순서(=인덱스)에 대응하도록 변수 idx도 활용하여 map에 insert한다.

#include <bits/stdc++.h>
 
using namespace std;
 
int n;
 
vector<int> v;
 
map<int, int> m;
 
void NextGreaterElement() 
{
    int idx = 0;
 
    stack<pair<int, int> > s;
 
    s.push({ idx++, v.at(0) });
 
    for (int i = 1; i < v.size(); i++)
    {
        while (!s.empty() && s.top().second < v.at(i))
        {
            m[s.top().first] = v.at(i);
            s.pop();
        }
 
        s.push({ idx++, v.at(i) });
    }
 
    while (!s.empty())
    {
        m[s.top().first] = -1;
        s.pop();
    }
 
    for (auto i : m)
        printf("%d ", i.second);
    printf("\n");
}
 
int main(void)
{
    int a;
 
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a);
        v.push_back(a);
    }
 
    NextGreaterElement();
 
    return 0;
}