백준 오큰수(17298) C++ 풀이

알고리즘 분류

자료 구조

스택

문제 해결 아이디어

stack을 이용하여 empty()가 아닌 동안 자기보다 큰 값이 나올 때까지 pop()하고
empty()가 되면 -1를 넣으면 된다.

코드

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

int n;
int arr[1000001];
int result[1000001];
stack<int> st;

int main()
{
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}

	for (int i = n - 1; i >= 0; i--)
	{
		while (!st.empty())
		{
			if (st.top() > arr[i])
			{
				result[i] = st.top();
				break;
			}
			else
				st.pop();
		}
		if (st.empty()) result[i] = -1;
		st.push(arr[i]);
	}

	for (int i = 0; i < n; i++)
	{
		cout << result[i] << ' ';
	}
}