https://www.acmicpc.net/problem/11003
11003번: 최솟값 찾기
N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.
www.acmicpc.net
이 문제는 우선순위 큐로 해결할 수도 있지만, 모노톤 덱을 이용하면 더 빠르다.
우선순위 큐를 활용하려 할 경우,
데이터가 들어왔을 때 우선순위 큐에 담고, 최솟값 찾을 때 이미 범위를 벗어났는지 여부만 확인해주면 된다.
모노톤 덱을 사용한다면,
크기가 증가하는 수열 형태로 덱을 만들어주면 된다. 차근 차근 오른쪽으로 넣어준다.
범위가 벗어났다면 왼쪽에서 버려주고, 작은 값이 들어왔다면 더 작은 값을 덱에서 찾을 때까지 오른쪽부터 계속 버려준다.
중요한 점은 왜 버릴 수 있는 지 이해해야 하는 것이다.
최솟값을 찾을 때, 현재 위치에서 L칸 앞까지의 값을 보기 때문에, 덱에 이미 존재하는 나보다 큰 수는 과감히 버릴 수 있다. 현재 위치의 값을 포함하는 범위라면 자신이 반드시 포함되기 때문에, 자신보다 큰 L칸 앞의 수들은 절대로 최솟값으로 선택될 수 없다. 그리고 자신을 넘어선 범위에서도 자신이 포함되는 한 자신보다 큰 L칸 앞의 수들은 여전히 절대로 최소값으로 선택될 수 없다. 그래서 그냥 버릴 수 있는 것이다.
만약 같은 수가 들어왔다면?
이번에도 나보다 먼저 나온 수는 버릴 수 있다. 위와 같은 이유이다.
<알고리즘>
모노톤 덱
<코드>
from collections import deque
import sys
si = sys.stdin.readline
dq, ans = deque(), []
n, l = [int(e) for e in si().split()]
arr = [int(e) for e in si().split()]
for i in range(n):
while dq and dq[-1][0] >= arr[i]:dq.pop()
if dq and dq[0][1] < i-l+1:dq.popleft()
dq.append([arr[i], i])
ans.append(dq[0][0])
print(*ans)
