[백준 11003번] 최솟값 찾기 (Python3)

from heapq import *

N,L = map(int,input().split())
seq = [*map(int,input().split())]

hq = []
minlist = [0]*N
for i in range(N):
  heappush(hq,(seq[i],i))
  while hq[0][1] <= i-L:
    heappop(hq)
  minlist[i] = hq[0][0]

print(*minlist)

 

문제를 보자마자 풀이가 떠오르긴 했는데, 너무 간단해서 이건 아니겠지? 하고 제출해봤는데 맞았다. ㄷㄷ

다만 pypy로만 통과가 되고 python으로는 시간초과가 발생하였다.

 

찾아보니 내 풀이는 시간복잡도가 O(NlogN)인데, 시간복잡도를 O(N)으로 구현하는 방법도 있다고 한다. 한번 알아봐야겠다.

 

 

오늘의 교훈) 더 빠른 구현방식을 생각해보자