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

안녕하세요 !

https://www.acmicpc.net/problem/11003

풀이

최솟값을 찾을 구간 L이 고정되어 있기 때문에 슬라이싱 윈도우로 풀 수 있는 문제였습니다.
배열의 마지막 원소값의 value가 현재 원소값 a[idx] 크면 삭제해주고, ( dq[-1][1] > a[idx] )
배열의 0번째 원소값의 idx 값이 L구간 이전의 값이라면 삭제해주어야 합니다. ( idx - dq[0][0] >= l )
즉, 마지막 원소값과 0번째 원소값을 삭제하면서 답을 구해야하므로 deque를 이용합니다.
이런식으로 구하면 dq에 저장된 값은 최솟값을 유지하게 됩니다.

# https://www.acmicpc.net/problem/11003
from collections import deque


def solution(n, l, a):
    d = [0] * n
    dq = deque()
    for idx in range(n):
        while dq and dq[-1][1] > a[idx]:
            dq.pop()

        while dq and idx - dq[0][0] >= l:
            dq.popleft()

        dq.append((idx, a[idx]))
        d[idx] = dq[0][1]

    print(*d)


if __name__ == '__main__':
    n, l = map(int, input().split())
    a = list(map(int, input().split()))
    solution(n, l, a)