[BOJ/C++] 17298 오큰수

N이 1,000,000이기 때문에 반복문을 사용하면 시간 초과가 발생합니다.

스택을 이용하여 해결할 수 있습니다.

1. 스택에 새로 들어오는 수가 top에 존재하는 수보다 크면 그 수는 오큰수가 된다.
2. 오큰수를 구한 후 수열에서 오큰수가 존재하지 않는 숫자에 -1을 출력한다.

// boj g4 17298
// 오큰수

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

using namespace std;


int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N;
	cin >> N;
	
	stack<int> s;
	vector<int> v(N, 0);
	vector<int> result(N, 0);

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

	result[N - 1] = -1;
	s.push(v[N - 1]);

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

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

		s.push(value);
	}

	for (auto it : result)
		cout << it << " ";

	return 0;
}