BOJ11003 최솟값 찾기

Hoeun Lee·2021년 9월 10일

덱 우선순위 큐 자료 구조

백준 알고리즘 풀이

목록 보기

29/34

문제

BOJ11003 최솟값 찾기
플래티넘V | 백준 11003 | Python3 파이썬 풀이

알고리즘

슬라이딩 윈도우 문제이다. 단 시간초과를 방지하기 위해 모든 값을 윈도우에 담지 않고, 필요한 값만 윈도우에 넣는다.

맨 처음 제출하여 시간초과를 받았고, 이를 해결하기 위해 알고리즘을 재설계했다.

문제에 나와 있는 예제를 예시로 들면, 초기 상태에서 윈도우가 우측으로 한 번 이동한 경우는 위와 같을 것이다.

이때, 윈도우가 한 번 더 움직이게 되면

윈도우는 5를 담아야 한다. 여기서 5를 담을 것인가? 담아야 한다. 만약 배열이 [1, 5, 9, 9, 9]인 경우, 5를 담지 않는다면 윈도우가 1을 지나버리면 윈도우에는 5가 남아있지 않기 때문에 최솟값이 5임을 알 수 없다.

그 다음인 2는 담을 것인가?

당연히 담아야 한다. 미래를 생각해보면, 2가 언젠가는 서브 배열의 최솟값이 된다. 그러면 그냥 윈도우에 지나가며 모든 값을 담고, 윈도우가 벗어난 값은 버리면 되는가?

아니다. 이러한 경우 시간초과가 발생한다. 시간 초과를 막기 위해 일종의 트릭을 적용한다. 필요 없는 값은 버리는 것이다. 과연 이 상태에서 필요 없는 값은 무엇인가? 바로 5이다. 5는 주변 길이 4의 어느 서브 배열에서도 최솟값이 아니다. 이렇게 필요없는 값을 어떻게 판단할 수 있을까?

바로 새로 들어온 값보다 큰 값이 있다면 그 값을 버리면 된다.

증명
먼저, 현재 스텝에 윈도우에 넣을 값을 $T$ , 그 값의 인덱스를 $t$ 라고 한다. 지금의 상태를 $t$ 스텝이라고 한다. 또한, 윈도우에서 버리고자 하는 값을 $S$ 라고 할 때, $S$ 는 현재 $t$ 스텝보다 일찍 들어왔으므로 그 값의 인덱스를 $s$ 라고 하면, $t > s$ 이다.
재귀적인 구조에 수학적 귀납법을 적용하여 생각해본다면 (현재 $t$ 스텝 이전에는 해당 스텝에서 해당 스텝에 넣을 특정 값보다 큰 값은 제거되었다고 가정하고) $S$ 가 최솟값이 될 수 있는 서브 배열의 인덱스는 $s$ 부터 $s + L$ 까지이다.
또한, $T$ 가 최솟값이 될 수 있는 서브 배열의 인덱스는 $t$ 부터 $t + L$ 이다. 이때, $t > s$ 이므로, $t + L > s + L$ 이다. 즉, 현재가 $t$ 스텝일 때, $t + L > s + L$ 이므로, 지금 $t$ 스텝으로부터 어느 값이 영향을 미치는 서브 배열의 길이는 $t + L$ 이 되므로, $T$ 가 최솟값인 동안은 $S$ 는 $T$ 와 항상 윈도우에 함께 있게 되며, $S$ 는 $t - s + L$ 스텝 뒤에 윈도우에서 사라진다. 이 말은, 앞으로 $t - s + L$ 스텝 동안은 적어도 $S$ 가 최솟값이 될 일은 없다( $t - s +L < t + L$ 이므로)는 뜻이다.

쉽게 정리하면, 어떤 값이 윈도우에 들어올 때, 이미 윈도우에 그 값보다 큰 값이 있다면, 그 큰 값의 인덱스는 새로 들어온 값의 인덱스보다 작으므로, 윈도우에 먼저 나가게 되고, 적어도 그 동안은 큰 값이 최솟값이 될 수 없다는 뜻이다.

위와 같은 증명을 통해 해당 스텝에서 윈도우에 넣을 때, 그 들어오는 값보다 큰 값을 전부 제거한다. 즉, 위 상태에서는 2가 들어오는데, 2보다 큰 값인 5를 제거한다. 미래를 상상해보면 5를 제거하지 않더라도, 2보다 5가 먼저 윈도우에서 사라지는데 5가 사라지기 전에 2로 인해 5가 최솟값이 될 일은 발생하지 않는다.

위 상태까지 진행하면 윈도우에는 위와 같이 3, 2, 1이 남게 된다. 다음 스텝에서는 1은 윈도우에서 벗어나므로 제거하고 6을 넣으면 된다.

벗어난 값 제거는 윈도우에 값과 인덱스를 함께 넣어, 윈도우에서 벗어난 인덱스를 제거해준다.

while dq:
    # 인덱스가 벗어난 값은 윈도우에서 제거
    if abs(i - dq[0][1]) >= L:
        dq.popleft()
    else:
        break

윈도우는 덱(deque)을 사용한다. 덱 원소들은 항상 정렬된 상태가 유지된다.

증명 (수학적 귀납법)
base : 맨 첫 값이 들어오면 윈도우에는 값이 단 한개 있으므로 정렬된 상태이다.
step : $t$ 스텝에서 $T$ 가 들어올 때, 위 알고리즘에 의해 $T$ 보다 큰 값은 전부 제거된다. 그러면, 배열에는 $T$ 보다 작은 값만 존재한다. 그리고, $T$ 는 배열의 맨 뒤에 들어간다. 그러면 배열에서 $A_i < T, i < t$ ( $T$ 의 인덱스보다 작은 인덱스를 가진 모든 값은 $T$ 보다 작다)가 성립한다.
$t + 1$ 스텝에서 $K$ 가 들어올 때, 만약 $T > K$ 라면 $T$ 는 제거되고 $K$ 가 들어오므로 성립.
$T < K$ 라면 $T$ 뒤에 $K$ 가 들어오고, $A_i < T < K, i < t < t + 1$ 이므로 성립.
위의 step에 의해 모든 step에 대해 성립(덱 원소는 항상 정렬된 상태)한다.

위 증명에 의해, 배열의 맨 뒷 값을 비교하고 제거(pop)하면 큰 값을 $O(1)$ 에 제거할 수 있다.
또한, 최솟값은 배열에 맨 앞(인덱스 0)에 위치한다.

while dq:
    if dq[-1][0] > A[i]:
        dq.pop()
    else:
        break

시간 복잡도
for loop : $O(N)$
deque push, pop : $O(1)$

한 루프 내에 최소 0번의 pop 최대 4번의 pop + 1번의 push가 발생하지만, 모두 상수 시간이므로 시간 복잡도는 $O(N)$ 이다.

코드

import sys
from collections import deque

input = sys.stdin.readline

N, L = map(int, input().split())
A = [0] + list(map(int, input().split()))

dq = deque()

for i in range(1, N + 1):
    # pop bigger values than Ai
    while dq:
        if dq[-1][0] > A[i]:
            dq.pop()
        else:
            break
    
    # print("-"*10)
    # print(dq)
    # popleft past values
    while dq:
        if abs(i - dq[0][1]) >= L:
            dq.popleft()
        else:
            break
    
    # print(dq)
    dq.append([A[i], i])
    print(dq[0][0], end=' ')