[BaekJoon] 17298번 : 오큰수

17298번 : 오큰수

[BaekJoon] 2493번 : 탑 문제와 같은 유형의 문제이다. 탑은 왼큰수 느낌..

말 그대로 오른쪽에 있으면서 나보다 큰 수 중에서 가장 왼쪽에 있는 수를 찾으면 O(N^2) 되어버려 시간초과가 발생한다.

스택을 사용하면 되는데 알고리즘은 다음과 같다.

주어진 수열을 역방향으로 돌면서 작업을 수행한다.

1. 큰 수 스택의 top 보다 내가 크거나 같으면 큰 수 스택의 top 이 나보다 큰 수가 나올 때 까지 pop 한다.
2. 큰 수 스택이 비어있으면 답에 -1 을 넣고 큰 수 스택에 나를 넣는다.
3. 큰 수 스택이 비어있지 않다면 큰 수 스택의 top 을 답에 넣고 나를 큰 수 스택에 넣는다.

글로 되어있어 이해가 잘 안갈 수 있지만 손으로 그려서 직접 해보면 쉽게 알 수 있다.

---

import sys


def solution():
	answer = []
	max_num = []

	for num in reversed(arr):
		while max_num and max_num[-1] <= num:
			max_num.pop()

		if max_num:
			answer.append(max_num[-1])
			max_num.append(num)

		if not max_num:
			answer.append(-1)
			max_num.append(num)

	return list(reversed(answer))


if __name__ == '__main__':
	n = int(input())
	arr = list(map(int, sys.stdin.readline().rsplit()))

	print(*solution())