[백준 / python] 17298. 오큰수

백준 17298. 오큰수

 

첫 번째 시도

from collections import deque
import sys
input = sys.stdin.readline

ans = []
t = int(input())
dq = deque((map(int, input().split())))
for i in range(t):
    cmp = dq.popleft()
    res = []
    for elem in dq:
        if elem > cmp: res.append(elem)
    if len(res): ans.append(res[0])
    else: ans.append(-1)
print(*ans)

위 풀이로 접근하게 되면 O(N^2)이므로 시간 안에 문제를 풀 수 없다. 따라서 다른 풀이가 필요하다.

두 번째 시도

import sys
input = sys.stdin.readline

n = int(input())
li = list(map(int, input().split()))

stack = []
ans = [-1]*n

for i in range(n):
    while stack and li[stack[-1]] < li[i]:
        ans[stack.pop()] = li[i]
    stack.append(i)
print(*ans)

위 풀이의 핵심은 스택을 이용하여 필요한 만큼만 저장하고 활용한다는 것이다.