[스택심화]17298-오큰수

오~ 큰 수?

오큰수? 육큰수는요? 깔깔깔~

 

1. 아이디어

스택 관련하여 유형을 익힐 수 있는 오큰수 문제이다. 오큰수 문제는 간단한 아이디어로 시작된다.

느낌상으로만 보자면 동적 계획법과 비슷한 느낌도 존재한다.

뒤쪽부터 시작하여 스택에 추가한 뒤, pop()해주면서 가장 오른쪽에 있는 값을 찾으면 되지 않을까?

 

2. 정리

3. 코드

import sys
input = sys.stdin.readline
print = sys.stdout.write
n = int(input().rstrip())
num = list(map(int, input().rstrip().split()))
stack = []
value = [-1]*(n+1)
for i in range(n-1, -1, -1):
    while True:
        if len(stack) == 0:
            break
        a = stack.pop()
        if num[i] < a:
            value[i] = a
            stack.append(a)
            break
    stack.append(num[i])
for i in range(n):
    print(str(value[i])+" ")