백준 11003 최솟값 찾기 - 파이썬

import sys
from collections import deque

input = sys.stdin.readline

N, L = map(int,input().split())
arr = list(map(int,input().split()))
D = []
q = deque([])

for i in range(N):
    # 덱이 비어있지 않고 덱의 맨 뒤가 추가하려는 원소보다 크면 제거 (덱을 오름차순으로 유지하기 위함)
    while q and q[-1][0] > arr[i]:
        q.pop()
    q.append([arr[i], i])
    # 덱의 맨 앞 원소의 인덱스가 슬라이딩 윈도우를 벗어났으면 제거
    if q[-1][1] - q[0][1] == L:
        q.popleft()
    D.append(q[0][0]) # 덱의 맨 앞은 항상 슬라이딩 윈도우 내 최솟값
print(*D)

슬라이딩 윈도우 활용 문제

 

덱의 맨 앞을 원소를 항상 슬라이딩 윈도우 내의 최솟값으로 유지하는 방식이다.

 

1. while 루프를 통해 추가하려는 원소와 덱의 맨 뒤에 있는 원소를 비교하여 덱 내의 원소가 더 큰 경우 pop해서 제거

2. 덱의 맨 앞과 맨 뒤 원소의 인덱스를 비교하여 슬라이딩 윈도우를 벗어났으면 맨 앞 원소 제거

3. 위의 과정을 통해 덱의 맨 앞 원소를 항상 슬라이딩 윈도우 내 최솟값으로 유지.