[백준 11003번] 최솟값 찾기

	# 백준 11003번 링크 N개의 수 A1, A2, ..., AN과 L이 주어진다.Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net

 

 

 

Key point

• 슬라이딩 윈도우 기법을 사용하여 하나씩 밀면서 비교한다
• deque에 하나씩 넣어 현재 deque에 남은 숫자와 비교하여 더 작으면 보관한다
• 문제의 범위가 넘어가면 popleft를 사용하여 deque에서 뺀다.

 

문제 코드

 

from collections import deque

N,L = map(int ,input().split())
A=list(map(int ,input().split()))
mydeque= deque()

for i in range(N): 
	#현재 보관된 숫자보다 작으면 그전에 있는 숫자빼기
    while mydeque and mydeque[-1][0]>A[i]:
        mydeque.pop()
    #숫자 넣기
    mydeque.append((A[i],i))
    #가장적은 숫자가 범위에서 나가면 제거
    if mydeque[0][1]<=i-L:
        mydeque.popleft()
    print(mydeque[0][0], end=' ')