[백준] 11003 최솟값 찾기, python

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

 

 

 

구간의 최솟값을 찾는 문제이다.

파이썬 내장함수 min을 쓰게 되면 O(n)을 n 번하게 되어 시간초과가 나게 된다.

 

이 문제는 모노토닉 큐를 사용하여 해결할 수 있다.

모노토닉 큐(단조 큐)란 큐안의 원소들이 항상 오름차순, 또는 내림차순을 유지하도록 관리되는 큐이다.

이 문제에서는 최솟값을 찾아야 하므로 큐가 오름차순을 유지되도록 관리한다.

 

모노토닉 큐에는 인덱스와 값을 같이 넣어주어야 한다. 왜냐하면 윈도우의 크기가 범위를 벗어나게 되면, 큐의 맨 왼쪽값(구간의 최솟값)이 범위를 벗어나게 되면 제외해 주어야하기 때문이다.

윈도우를 오른쪽으로 이동시키고 윈도우에 추가되는 값과 모노토닉 큐의 맨 오른쪽값을 비교한다. 만약 추가되는 값이 더 작다면, 큐의 오른쪽에서 빼낸다. 현재 추가되는 값보다 큰 값들은 최솟값에 영향을 주지 않기 때문이다. 이를 반복해서 현재 추가되려는 값보다 큰 값을 모두 빼낸다. 

이렇게 되면 최솟값 모노토닉 큐는 항상 오름차순을 유지하게 되고, 큐의 맨 왼쪽값(q [0]) 이 최솟값이 된다.

 

 

예제 입력 1의 경우를 보면

처음엔 모노토닉 큐가 비어있으므로 (인덱스, 값)인 (0,1)을 넣어준다.

 

 

 

 

 

모노토닉 큐의 마지막 값보다 넣으려는 값이 크므로 (1,5)를 넣어준다.

 

 

 

 

 

넣으려는 값 2가 모노토닉큐의 마지막 5보다 작다. 모노토닉큐에서 2보다 작거나 같은 값이 나올 때까지 빼준다. 다 빼고 나서 큐에 (2,2)를 넣어준다.

 

 

 

 

 

윈도우의 크기가 이동하면서  큐의 맨 왼쪽값(최솟값)의 인덱스가 윈도우 범위에서 벗어났으므로 큐에서 제외해 준다. 넣으려는 값 3은 큐의 마지막 값보다 크므로 (3,3)을 넣는다.

 

 

 

 

 

(2,2)는 윈도우의 범위를 벗어났으므로 큐에서 제외해준다. 모노토닉 큐의 마지막 값보다 넣으려는 값이 크므로 (4,6)를 넣어준다.

 

 

 

 

 

(3,3)는 윈도우의 범위를 벗어났으므로 큐에서 제외해준다. 모노토닉 큐의 마지막 값보다 넣으려는 값이 작으므로 (4,6)를 큐에서 제외해준다. (5,1)을 넣는다.

 

 

이 과정에서 모노토닉 큐는 항상 오름차순을 유지하게 되고 큐의 맨 왼쪽값이 최솟값이 된다.

 

 

 

import sys
from collections import deque
input = sys.stdin.readline

n, l = map(int, input().split())
arr = list(map(int, input().split()))

q = deque()

# 모노토닉 큐를 사용하여 구현
for i in range(n):
    while q and q[-1][1] > arr[i]:
        q.pop()
    
    q.append((i, arr[i]))

    while q[0][0] <= i-l:
        q.popleft()

    print(q[0][1],end = ' ')