17298 - 오큰수

코드

#include <iostream>
#include <stack>
using namespace std;

int N;
int arr[1000001];
stack<int> s;
stack<int> ans;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	
	for (int i = N - 1; i >= 0; i--) {
		while (!s.empty() && s.top() <= arr[i]) {s.pop();}
		if (s.empty()) {ans.push(-1);}
		else { ans.push(s.top()); }
		s.push(arr[i]);
	}
	while (!ans.empty()) {
		cout << ans.top() << " ";
		ans.pop();
	}
	return 0;
}

이 문제는 N이 최대 1,000,000이기 때문에 일반적인 n^2으로 풀면 시간 초과가 나와서
스택을 이용하여 O(N)에 풀어내야하는 문제이다.

핵심 알고리즘
1. 맨 뒤 부터 비교하며 arr[i]보다 s.top()이 커질 때가 언제인지 찾는 것입니다.
2. s.pop()한 숫자들을 버려도 상관 없다!

• because pop한 숫자들은 arr[i]보다 작기 때문에

위의 논리 대로 수행하면 스택 s에는 top이 가장 작고 오름차순으로 정렬된다.