백준 11003번 최솟값 찾기 파이썬

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

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=' ')

---

Review

 

주어진 전체 Array = [1, 5, 2, 3, 6, 2, 3, 7, 3, 5, 2, 6]

 L (Window 크기) = 3

Window: [0, 0, 1]  → Min value: 1
Window: [0, 1, 5]  → Min value: 1
Window: [1, 5, 2]  → Min value: 1
Window: [5, 2, 3]  → Min value: 2
Window: [2, 3, 6]  → Min value: 2
Window: [3, 6, 2]  → Min value: 2
Window: [6, 2, 3]  → Min value: 2
Window: [2, 3, 7]  → Min value: 2
Window: [3, 7, 3]  → Min value: 3
Window: [7, 3, 5]  → Min value: 3
Window: [3, 5, 2]  → Min value: 2
Window: [5, 2, 6]  → Min value: 2

구간을 정해 정렬로 푸는 건 Nlog(N)의 시간 복잡도가 걸린다. -> 시간초과

O(N)으로 해결할 수 있는 방법으로 풀어야 한다.

deque을 활용하여 풀어야 시간 초과가 뜨는 것을 해결할 수 있다.

세가지 과정만 알면 된다.

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

1. dq의 원소가 있고 && dq에 들어오는 값이 dq 끝값보다 큰 원소가 있다면 → dq.pop()
    < 값에 집중 >
  최솟값 찾는 과정 : 현재 or 옆으로 가는 window에선 최솟값이 될 수 없음

2. 원소 삽입

3. dq에서 가장 오래된 원소( 맨 앞 원소 ) 가 Window 밖에 있는 경우( index를 벗어나는 경우 )  dq.popleft()
     < index에 집중 >
    윈도우 길이가 초과 한다는 의미 - > index 가 가장 작은 원소가 창밖에 있다는 뜻

 

과정을 그림으로 그리면 아래와 같아진다.

 

결론:

슬라이딩 윈도우 기법은 이러한 슬라이딩 윈도우 최소 문제를 포함하여 다양한 문제를 효율적으로 해결할 수 있는 강력한 알고리즘 접근법이다.

관련 요소의 deque를 유지함으로써 비용이 많이 드는 계산을 피하고 선형 시간 내에 문제에 대한 답을 효율적으로 찾을 수 있다.