[C++] 백준 17298번 - 오큰수

처음에는 이중 for문 즉, O(N^2)로 풀었는데 시간초과가 떠버렸다.

어떻게 이걸 O(N)으로 풀지, 그리고 어떻게 스택으로 풀지 고민하다가 결국 

다른 분의 블로그를 참조했다.

 

원리는 생각보다 간단했다. stack에 저장하면서 stack에 있는 값이랑 비교하면서 큰 값 나올때까지 pop하기

 

답을 안보고 싶은데 진짜 1시간 동안 못풀면 계속 보게된다;;;;

 

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

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

int main() {
	cin >> N;

	for (int i = 0; i < N; i++)
		cin >> seq[i];

	for (int i = N - 1; i >= 0; i--) {
		while (!s.empty() && s.top() <= seq[i])
			s.pop();

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

		s.push(seq[i]);
	}

	for (int i = 0; i < N; i++)
		cout << ans[i] << " ";
}