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

---

문제 분석

일정 범위 안에서 최솟값을 구하는 문제이므로 슬라이딩 윈도우와 정렬을 사용하면 된다.
윈도우의 크기는 문제에서 최솟값을 구하는 범위가 i-L+1부터 i까지 이므로 L로 생각하면 된다.
최솟값을 찾기 위한 정렬의 경우 일반적인 정렬에서는 O(nlogn)의 시간 복잡도를 가지므로 N과 L의 최대 범위가 5,000,000인 이 문제에서는 정렬을 사용할 수 없다. 따라서 O(n)의 시간 복잡도로 해결해야 하며, 슬라이딩 윈도우를 덱으로 구현하여 정렬효과를 볼 수 있다는 것을 활용해 덱을 통해 해결하도록 한다.

---

소스 코드

# 최솟값 찾기
from collections import deque
import sys
input = sys.stdin.readline

N, L = map(int, input().split())
numList = list(map(int, input().split()))
deq = deque()

for i in range(N):
    while len(deq) != 0 and deq[-1][1] > numList[i]:
        deq.pop()
    deq.append((i+1, numList[i]))

    while (i+1) - deq[0][0] >= L:
        deq.popleft()
    print(deq[0][1], end=' ')

이 문제의 핵심은 정렬 알고리즘을 사용하지 않고도 슬라이딩 윈도우와 덱을 이용해 정렬 효과를 만들어 내는 것이다.