[11003번] 최솟값 찾기 (슬라이딩 윈도우, 덱)

11003번: 최솟값 찾기

 

분석

• 일정 법위에서 최솟값을 찾는 문제 : 슬라이딩 윈도우/ 정렬
• 정렬
  • N과 L의 범위가 5,000,000인 문제에서 정렬 사용 불가
• 슬라이딩 윈도우
  • 덱으로 구현하여 정렬 효과
  • i-L+1 ~ i 까지 이므로 윈도우 크기는 L로 생각

예시
N: 12, L : 3, A: 1 5 2 3 6 2 3 7 3 5 2 6

1. 새 노드 (3,2)가 저장될 때 뒤에서부터 비교 시작
: (2,5)는 (3,2)보다 숫자가 크므로 덱에서 제거 (최솟값 가능성 없는 데이터 삭제)
(1,1)(2,5)(3,2)
뒤에서 부터 비교

2. window 크기(3) 밖 데이터 삭제
: index비교
(1,1)(2,5)(3,2)(4,3)

 

풀이

# 슬라이딩 윈도우
# dequeue 사용
from collections import deque
N, L = map(int, input().split())
deque = deque()
list = list(map(int, input().split()))



for i in range(N):

    # 덱의 마지막 위치에서부터 현재 값보다 큰 값은 덱에서 제거
    while deque and deque[-1][0] > list[i]:
        deque.pop()

    # 덱의 마지막 위치에 현재 값 저장
    deque.append((list[i],i))

    # 덱의 1번째 위치에서부터 L의 범위를 벗어난 값을 덱에서 제거
    if deque[0][1] <= i - L:
        deque.popleft()

    # 덱의 1번째 데이터 출력
    print(deque[0][0], end=' ')