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)으로 구현하는 방법도 있다고 한다. 한번 알아봐야겠다.
오늘의 교훈) 더 빠른 구현방식을 생각해보자