🟠 슬라이딩 윈도우문제-최솟값 찾기

Deque사용하기

덱(Deque)이란 double-ended queue를 줄여서 표현한 것으로 양방향으로 넣고 뺄 수 있다.
따라서 deque은 스택과 큐의 특성을 모두 갖고 있으며, 둘을 조합한 형태의 자료구조로 이해하면 된다.

Method Explanation

• deque.append(item) 오른쪽 끝에 새로운 원소를 삽입한다.
• deque.appendleft(item) 왼쪽 끝에 새로운 원소를 삽입한다.
• deque.pop() 오른쪽 끝의 원소를 제거 후 반환한다.
• deque.popleft() 왼쪽 끝의 원소를 제거 후 반환한다.
• deque.extend(array) 주어진 array 배열을 순환하며 오른쪽에 추가한다
• deque.extendleft(array) 주어진 array 배열을 순환하며 왼쪽에 추가한다.
• deque.insert(n, item) n번 index에 원소를 추가한다.
• deque.remove(item) 입력한 원소를 삭제한다. 같은 원소가 있을 경우 왼쪽부터 삭제된다.
• deque.rotate(n) n만큼 원소의 위치를 회전한다. (양수 : 시계방향, 음수 : 반시계 방향)
• deque.clear() 모든 원소를 제거한다.
• deque.reverse() 원소의 위치를 좌우 반전시킨다.

deque에 들어가는 원소 (index, value) !!

🦊[문제]: 최솟값 찾기

백준 11003번

🐙[해설코드]

import sys
from collections import deque
 
input = sys.stdin.readline
 
N, L = map(int, input().split())
A = list(map(int, input().split()))
 
dq = deque()
for i in range(N):
	
    while dq and (dq[-1][1] > A[i]): # 1
        dq.pop()
	
    dq.append((i + 1, A[i]))         # 2
	
    if dq[-1][0] - dq[0][0] >= L:    # 3
        dq.popleft()
 
    print(dq[0][1], end=' ')