문제 출처

1. 문제설명

  • 수열이 N개 주어진다.
  • 각 원소의 오른쪽 수 중 가장 큰 수가 오큰수가 된다.
  • 각 원소의 오큰수를 구하라.
    • 오큰수가 없다면 -1로 대체



2. 알고리즘 설계

  • 스택 문제이다.
  • 이전 옥상정원 문제와 비슷하게 풀이할 수 있다.



3. 로직

  • 스택에 값을 push한다.
  • push된 값 중에 현재 값보다 작으면 스택에서 제거한다.
  • 제거된 스택의 top 값이 오큰수가 된다.



4. 전체 코드

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

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n, tmp;
	cin >> n;

	vector<int> v(n), ans(n);

	for (int i = 0; i < n; i++) cin >> v[i];

	stack<int> st;
	for (int i = v.size() - 1; i >= 0; i--) {
		while (!st.empty() && st.top() <= v[i]) st.pop();

		if (!st.empty()) ans[i] = st.top();
		else ans[i] = -1;

		st.push(v[i]);
	}

	for (int a : ans) cout << a << ' ';
	return 0;
}