[백준][Python] 11003 최솟값 찾기 - 덱(Deque)으로 정렬하기

 

문제

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

11003번: 최솟값 찾기

---

설계

 

N개의 수가 주어지고, 숫자 L이 주어지며 주어진 $D_{i}$ 의 최솟값들을 출력하는 문제이다.

기본적인 구성은 위의 그림과 같다.

 

L = 2일 때, $D_{i}$ 는 $A_{i-1}$ ~ $A_{i}$ 의 범위 중 최솟값이 되고,

L = 3일 때, $D_{i}$ 는 $A_{i-2}$ ~ $A_{i}$ 의 범위 중 최솟값이 된다.

이를 알아보기 쉽게 표현하면 다음과 같다. (예제에서는 L = 3 이다. 예제를 예로 들어 설명하겠다.)

파란색 네모가 창문이 움직이는 것 같다고 해서 '슬라이딩 윈도우' 라고 부른다.

 

그렇다면 제일 먼저 드는 생각이, 3의 크기로 수열 A를 순회하면서 최솟값을 찾으면 될 것 같다는 생각이 든다.

그러나 위와 같이 설계를 하면 시간 복잡도가 $O( n^{2} )$이 되는데, 이 문제는 입력이 최대 5백만 개 이다.

25조 번의 연산을 했다간 시간초과고 뭐고 우리의 CPU가 잿더미가 되버리고 말 것이다...

우리의 컴퓨터는 소중하니까 이 문제는 $O(n)$의 시간 복잡도로 해결해야 한다.

---

그렇다면 시간 복잡도를 줄여보자

수열 A를 순회하면서 $O(n)$의 시간이 걸리는 것은 불가피하다.

결국 우리가 시간 복잡도를 줄일 수 있는 부분은 슬라이딩 윈도우에서의 최솟값을 $O(1)$의 시간복잡도로 꺼내는 것이다.

그렇다면 수열의 입력과 동시에 정렬을 시키고, 최솟값을 바로 꺼낼 수 있는 스택이나 큐, 덱을 사용하면 되지 않을까?

(덱이 무엇인지 모르겠다면 아래 게시글을 참고하자)

https://pink-saurus.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0Python-%EB%8D%B1-Deque

[자료구조][Python] 덱 (Deque)

---

덱(Deque)으로 수열 바로 정렬하기

덱에 수열의 원소를 삽입한다. 덱의 맨 뒤부터 맨 앞까지 비교를 해서 삽입하는 값보다 크면 pop()을 실행한다.

여기서 슬라이딩 윈도우의 크기도 고려를 해야한다. 인덱스도 노드에 같이 넣어 한 노드를 (인덱스, 값)의 튜플 형태로 만들자.

그렇다면 위의 비교하는 구간이 끝나면 맨 앞과 맨 뒤의 인덱스의 차이를 비교해서

슬라이딩 윈도우의 크기(L)가 되도록 popleft()를 실행하면 될 것이다.

---

코드

import sys
from collections import deque

input = sys.stdin.readline

N, L = map(int, input().split())
array = list(map(int, input().split()))

deque = deque()

for i in range(N):
    while deque and deque[-1][1] > array[i]:
        deque.pop()
    deque.append((i, array[i]))
    if deque[0][0] <= i - L:
        deque.popleft()
    print(deque[0][1], end=" ")