2493번 탑

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

오큰수 복습 필수 stack 스택 nge 코테 코딩 boj 백준

비슷한 문제 : https://hsdevelopment.tistory.com/374

개념(Next Greater Element) : https://hsdevelopment.tistory.com/373

#include<bits/stdc++.h>
 
using namespace std;
 
int n;
vector<pair<int, int> > v;
map<int, int> m;
stack<pair<int, int> > st;
 
void nge()
{
    int idx = n;
    st.push({ idx--, v[0].second });
 
    for (int i = 1; i < n; i++) {
        while (!st.empty() && st.top().second < v[i].second)
        {
            m[st.top().first] = v[i].first;
            st.pop();
        }
 
        st.push({ idx--, v[i].second });
    }
    
    while (!st.empty())
    {
        m[st.top().first] = 0;
        st.pop();
    }
 
    for (auto i : m) {
        printf("%d ", i.second);
    }
 
    printf("\n");
}
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\buba.in.6", "r", stdin);
    cin.tie(0);
 
    scanf("%d", &n);
 
    v.assign(n, { 0, 0 });
    int idx = 1, input;
    for (int i = n - 1; i >= 0; i--) {
        scanf("%d", &input);
        v[i] = { idx++, input };
    }
 
    nge();
 
    return 0;
}