[백준-11003] 최솟값 찾기1

문제

N개의 수 A1, A2, ..., AN과 L이 주어진다.

Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오.
이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

 

입력

첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000)

둘째 줄에는 N개의 수 Ai가 주어진다. (-109 ≤ Ai ≤ 109)

 

출력

첫째 줄에 Di를 공백으로 구분하여 순서대로 출력한다.

 

정답

import sys
input = sys.stdin.readline

from collections import deque
mydeque = deque()

N, L = map(int,input().split())
lists = list(map(int,input().split()))


for i in range(N):
	# 새로운 값이 기존의 값보다 커질때까지 기존의 값(끝부분부터)제거 
    while mydeque and mydeque[-1][0] > lists[i]:
        mydeque.pop() # 잘라내기
    mydeque.append((lists[i],i)) # 새로운 값 입력
    
    # 슬라이딩 윈도우가 인덱스 범위에서 벗어난 경우 제거
    if mydeque[0][1]<= i-L:
        mydeque.popleft()
    print(mydeque[0][0],end=" ")