오큰수 (feat. 백준, 17298번)

오큰수
https://www.acmicpc.net/problem/17298

17298번: 오큰수

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <stack>
#include <string.h>
using namespace std;
int arr1[1000000], arr2[1000000];
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	memset(arr1, 0, sizeof(arr1));
	memset(arr2, 0, sizeof(arr2));
	register int N;
	stack<int> ans;
	cin >> N;
	for (register int n = 0; n < N; ++n)
		cin >> arr1[n];
	ans.push(arr1[N - 1]);
	arr2[N - 1] = -1;
	for (register int i = N - 2; i >= 0; --i) {
		while (!ans.empty() && arr1[i] >= ans.top())
			ans.pop();
		arr2[i] = ans.empty() ? -1 : ans.top();
		ans.push(arr1[i]);
	}
	for (register int i = 0; i < N; ++i)
		cout << arr2[i] << " ";
	return 0;
}
// *&)*@*

1. 입력받은 값중 가장 우측은 무조건 -1이 됩니다.
2. 그리고 우측의 값을 스택에 삽입합니다.
3. 우측부터 좌측으로 생각해봅니다. 해당 값은 A라고 하겠습니다.
4. A와 스택의 top을 비교해봅니다. A가 스택의 top보다 크거나 같다면 (A>=stack.top) 스택을 pop 합니다.
5. 스택이 비었다면 -1을, 아니라면 top이 A보다 큰 값입니다.
6. A를 스택에 삽입하고 4번부터 반복합니다.