[Python] 백준 11003번 최솟값 찾기

# 최솟값 찾기
# N개의 수와 L이 주어진다. D(i) = A(i-L+1) ~ A(i) 중의 최솟값이라고 할 때, D에 저장된 수를 출력하시오.
# 첫째 줄에는 N, L이 주어지고, 둘째 줄에는 N개의 수가 주어진다.

from collections import deque

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

for i in range(N):
    while mydeque and mydeque[-1][0] > now[i]:
        mydeque.pop()
    mydeque.append((now[i], i))
    if mydeque[0][1] <= i - L:
        mydeque.popleft()
    print(mydeque[0][0], end=' ')

슬라이딩 윈도우와 덱을 이용한 문제

슬라이딩 윈도우를 덱으로 구현하여 정렬 효과를 볼 수 있다.

 

[1] 새로운 요소를 추가할 때, 덱의 끝 요소와 크기를 비교한다.

새로운 요소의 크기가 더 크다면 그냥 추가하고, 더 작다면 기존 끝 요소를 제거한 후 추가한다.

 

[2] 덱의 첫 요소의 인덱스 번호를 확인한다.

인덱스 번호가 슬라이딩 윈도우의 크기보다 크다면(슬라이딩 윈도우의 크기: L, 총 개수는 i - L보다 적어야 함) 첫 요소를 제거한다.

 

덱의 첫번째 요소는 항상 최소값이 되므로(과정[1]을 통해 추가할 때마다 본인보다 큰 요소들 제거), 첫 요소의 값을 출력한다.

 

 

파이썬에서 덱을 사용하기 위해서는 collections 모듈의 dequq 클래스를 임포트 해야 한다.

from collections import deque