백준 17298번 - 파이썬

 

17298번: 오큰수

입력 최대 수가 100만 이기 때문에 시간 복잡도를 잘 고려해야한다. for 중복문은 사용할 수 없고 자료구조 stack을 이용했다.

아래 그림은 내가 생각한 풀이를 그림으로 나타냈다.

그림 풀이

내 코드

import sys
n = int(input())
stack = list(map(int,sys.stdin.readline().split()))
ans = []
stack2 = []
ans.append(-1)
stack2.append(stack.pop())

while stack:
    val = stack.pop()
    if val < stack2[-1]:
        ans.append(stack2[-1])
        stack2.append(val)
    else:
        while stack2 and val >= stack2[-1] :
            stack2.pop()
        if stack2:
            ans.append(stack2[-1])
        else:
            ans.append(-1)
        stack2.append(val)

ans.reverse()
for val in ans:
    print(val, end = ' ')