백준 LG전자대비 / 골드 4 / 17298 오큰수 / C++ [스택]

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

풀이

lower_bound 어쩌구 하면서 실컷 이상하게 풀다가, 예전에 알고리즘 수업 들을 때 봤던 문제라는 생각이 들었다.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    
    int n, num, idx;
    cin >> n;
    vector<int> v(n, -1); // 초기화 하는 방법 몰라서 시간 뺐겼다.
    
    stack<pair<int, int>> s;
    for (int i = 0; i < n; i++) {
        cin >> num;
        while(s.size() != 0 && s.top().first < num) {
            idx = s.top().second;
            v[idx] = num;
            s.pop();
        }
        s.push(pair<int, int>(num, i));
    }
    for (int x : v) {
        cout << x << '\n';
    }
}