[Python/백준] 17298 오큰수

https://www.acmicpc.net/problem/17298

17298번: 오큰수

<문제 해설>

stack 문제이다. 오른쪽의 수를 stack에 저장하는 방식으로 나아가야한다.

출력할 값은 N개 만큼의 0을 가지고있는 output배열에 기록한다.

주어진 수열의 오른쪽 부터 시작해서 전체를 반복한다.

stack에 현제값이랑 비교해서 작거나 같은 값이 있으면 pop하고 아닐경우 현제 값을 stack에 넣어준다.

이떄 stack에 현제값이랑 비교해서 작은 값이 없다면 -1을 output에 기록하고 아닐경우 output에 stack의 마지막 값을 기록한다.

<예시>

N = 7
numbers = 4 3 2 1 2 3 4 

예시이다.

n = 6

stack이 비어있었기 떄문에 4를 stack에 넣고 output[n] 에는 -1이 들어간다.

n = 5

stack에 4가 3보다 크니 4를 output에 저장하고 stack에 3 넣어준다. 이런방식으로 n = 3 까지 진행된다.

n = 3

n = 2

stack이 현제 2랑 값이 같거나 작은 1,2 가 차래대로 빠진다 그후 2보다큰 3이 output에 저장된 후에 stack에 2를 넣어준다.

n = 0

이런방식으로 n=0까지 진행되고 stack이 비었으니 n=0자리에 -1이 들어간다.

<코드>

import sys

N = int(sys.stdin.readline())
numbers = list(map(int,sys.stdin.readline().split()))
output = [0]*N

right = []

for n in range(N-1,-1,-1):
    now = numbers[n]
    while(right):
        if right[-1] <= now:
            right.pop()
        else:
            break
    if len(right) == 0:
        output[n] = -1
    else:
        output[n] = right[-1]
    right.append(now)

print(*output)