[백준/17298][C++] 오큰수

문제

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

17298번: 오큰수

풀이

스택+그리디

뒤에서부터 거꾸로 스택에 집어 넣는다. 만약 스택이 비어있다? 그럼 ans배열에 -1을 저장한다.
스택에 뭐가 있는데, 내가 지금 따지는 수가 스택의 맨 위에 것보다 작거나 같다? 그럼 계속 pop한다.
왜냐면 내가 필요한건 지금 내가 따지는 수보다 큰거니까. 그리고 내가 지금 따지는 수를 stack에 넣는다.

이걸 시험 때 떠올릴 수 있을까?
연습을 훨씬 더 해야겠지..

코드

#include<bits/stdc++.h>
using namespace std;
int n;
int arr[1000001];
int ans[1000001];
stack<int> s;
int main(void) {
	ios_base::sync_with_stdio(0);
	cin.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]) {
			//stack에 뭐가 있는데 원하는게 아니면 계속 pop
			s.pop();
		}
		if (s.empty()) {
			//원하는게 결국 없었어?
			ans[i] = -1; //답은 -1
		}
		else {
			//원하는게 나왔어?
			ans[i] = s.top();
		}
		s.push(arr[i]);
	}
	for (int i = 0; i < n; i++) {
		cout << ans[i] << " ";
	}
}