백준 17298 오큰수 혼내주기

 

ps 처음 공부할 때 꾸역꾸역 블로그 찾아가면서 풀고 이해를 못했던 기억이 있는 문제였는데, 지금 풀어보니까 이렇게 쉬울 수가 없다...
스택에 넣을 때 마다 현재 숫자보다 작은 숫자를 다 pop해주면 되는 문제.

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
using namespace std;

int arr[1000001];
int n;

void input() {
    fastio;
    cin >> n;
}

int main() {
    input();

    stack<pair<int, int> > stk;
    for(int i = 0; i < n; ++i) {
        int num; cin >> num;
        
        while(!stk.empty() && stk.top().first < num) {
            arr[stk.top().second] = num;
            stk.pop();
        }
        stk.push({num, i});
    }

    while(!stk.empty()) {
        arr[stk.top().second] = -1;
        stk.pop();
    }

    for(int i = 0; i < n; ++i) {
        cout << arr[i] << " ";
    }
}