[17298] 오큰수 (C++)

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

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

	int n; cin >> n;
	vector<int> A(n, 0);
	vector<int> ans(n, 0);

	stack<int> st;
	st.push(0);

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

	for (int i = 1; i < n; i++) {
		while (!st.empty() && A[st.top()] < A[i]) {
			ans[st.top()] = A[i];
			st.pop();
		}
		st.push(i);
	}
	while (!st.empty()) {
		ans[st.top()] = -1;
		st.pop();
	}

	for (auto x : ans)
		cout << x << " ";
}

 

1. stack에 A의 index를 순서대로 push

2. stack이 비어있지 않고 A[i]이 A[st.top()] 보다 큰 경우 해당 index의 A 값을 ans에 입력

3. while loop가 종료된 후 stack이 비어있지 않다면 빌 때까지 ans에 '-1'을 입력