[C++] 백준 17298 오큰수

#include <iostream>
#include <stack>
 
int ans[1000001] = {};
int arr[1000001] = {};
 
int main()
{
	int N = 0;
	std::cin >> N;
 
	std::stack<int> stk = {};
 
	for (int i = 0; i < N; ++i)
	{
		std::cin >> arr[i];
	}
 
	for (int i = N - 1; i >= 0; --i)
	{
		while (!stk.empty() && stk.top() <= arr[i])
		{
			stk.pop();
		}
 
		if (stk.empty())
		{
			ans[i] = -1;
		}
 
		else
		{
			ans[i] = stk.top();
		}
 
		stk.push(arr[i]);
	}
 
	for (int i = 0; i < N; ++i)
	{
		std::cout << ans[i] << " ";
	}
 
	return 0;
}

스택을 이용해서 풀었어야 했습니다.

처음에 입력을 하고 뒤에서부터 찾아합니다.

앞쪽에서 검색을 하려면 가장 마지막 수를 찾기 위해서

다시 맨뒤로 돌아가야하기 때문에 뒤에서부터 stack에 추가합니다.

입력을 하기 전에 현재 수보다 스택 안에 있는 수가 큰지 확인을 해야합니다.

스택 안에 맨 위의 수(오른쪽으로 가장 큰 수)가 현재의 수보다 크다면

해당 순서에 맨 위의 수를 넣어놓고 현재 수를 stack에 추가합니다.

현재의 수보다 크지 않다면 현재의 수가 오른쪽에 있는 수 보다 더 크기 때문에

stack에서 현재의 수보다 더 큰 수가 나오기 전까지 빼줍니다.

stack에 현재 값보다 큰 수가 없는 경우는 해당 순서에는 -1을 넣어놓습니다.

그리고 다음 순서를 찾기 위해 stack에 현재 값을 넣어줍니다.