[BOJ] 17298. 오큰수

* 스택을 사용한다.

* 나중에 들어오는 수가 오큰수가 정해지기 때문에 스택을 이용해서 가장 최근 넣은 값과 (top) 현재 값을 비교한다. 

이전 값보다 더 큰 수가 들어오면 => 이전 값 수의 오큰수는 현재 값이다. 

 

* 더 큰 수가 없으면 -1이다. 

 

 

#include <iostream> #include <vector> #include <stack> #define MAXX 1000001 using namespace std; typedef pair<int, int> pp; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; int res[MAXX]; int num[MAXX]; stack<pp> st; for (int i = 0; i < n; i++) res[i] = -1; for (int i = 0; i < n; i++) { int x; cin >> x; while (!st.empty()) { if (st.top().second < x) { res[st.top().first] = x; st.pop(); } else break; } st.push(pp(i, x)); } for (int i = 0; i < n; i++) { cout << res[i] << ' '; } return 0; }