[백준] 17298 : 오큰수

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

17298번: 오큰수

---

코드

from collections import deque

N = int(input())
lst = list(map(int, input().split()))

dq = deque([])
NGE = [-1] * N

for i in range(N):
    while dq and lst[dq[-1][0]] < lst[i]:
        tmp_i, tmp_num = dq.pop()
        NGE[tmp_i] = lst[i]
    dq.append([i, lst[i]])

print(*NGE)

 

풀이

처음 문제를 풀 때 이중 for문을 이용해서 하나씩 비교하고, 현재 수에 대한 오큰수를 찾으면 for문을 벗어나서 다음 수로 넘어가도록 하였다. 이러한 경우 시간복잡도가 O(N)이기 때문에 시간초과가 발생하였다.

따라서, 현재 수에 대한 오큰수에서 '현재 수에 대해 오큰수가 무엇이지?'라는 관점이 아닌 '해당 오큰수를 가지는 수는 무엇이지?'와 같이 반대로 접근해야 한다. 예를 들어 오큰수 7에 대해 7이라는 오큰수를 가지는 수에는 어떤 것이 있는지 생각해보는 것이다. 따라서, 스택을 이용해서 이를 구현하면 된다. 스택의 경우, 시간복잡도가 O(1)이므로 결과적으로 시간복잡도는 O(N)이 된다.