슬라이딩 윈도우 최댓값은 길이 k의 구간을 한 칸씩 밀면서 매번 최댓값을 구하는 문제입니다. 단순히 매 구간을 다시 훑으면 O(nk)가 되고, 힙을 쓰면 오래된 값을 늦게 버리는 처리가 필요합니다.
덱 풀이의 핵심은 현재 윈도우에서 최댓값이 될 가능성이 있는 인덱스만 남기는 것입니다. 그래서 이 기법을 보통 monotonic deque라고 부릅니다.
슬라이딩 윈도우 최댓값 문제
예를 들어 배열이 [1, 3, -1, -3, 5, 3, 6, 7]이고 k가 3이면, 길이 3짜리 구간을 한 칸씩 옮기며 각 구간의 최댓값을 구해야 합니다.
구간마다 새로 정렬하거나 전부 훑으면 너무 느립니다. 필요한 것은 현재 구간에서 최댓값 후보만 유지하는 구조입니다.
왜 값이 아니라 인덱스를 저장할까
덱에는 값 자체보다 인덱스를 저장하는 편이 좋습니다. 값만 저장하면 그 값이 현재 윈도우 밖으로 나갔는지 알기 어렵습니다.
인덱스를 저장하면 덱의 맨 앞 인덱스가 i - k 이하인지 확인해서 오래된 후보를 바로 제거할 수 있습니다.
덱이 유지하는 두 가지 규칙
예제를 한 번 따라가면 덱 풀이가 훨씬 덜 추상적으로 보입니다. 덱에는 전체 윈도우가 아니라 최댓값 후보만 남습니다.
그림에서 새 값 5가 들어오는 순간, 그 앞에 있던 -1, -3은 앞으로 어떤 윈도우에서도 최댓값 후보가 되기 어렵습니다. 그래서 뒤에서 제거됩니다.
- 덱의 앞 인덱스가 윈도우 밖이면 제거한다.
- 새 값보다 작거나 같은 값의 인덱스는 뒤에서 제거한다.
- 현재 인덱스를 뒤에 넣는다.
- 윈도우 크기가 k 이상이면 덱 앞의 값이 현재 최댓값이다.
두 번째 규칙이 가장 중요합니다. 새 값이 더 크면, 그보다 왼쪽에 있으면서 더 작은 값은 앞으로 어떤 윈도우에서도 최댓값이 될 수 없습니다.
힙 풀이와 무엇이 다를까
힙 풀이가 틀린 것은 아닙니다. 다만 이 문제에서는 윈도우가 한 칸씩 이동한다는 순서 정보가 강하게 주어져 있습니다. 덱은 이 순서를 그대로 이용하기 때문에 더 직접적인 풀이가 됩니다.
힙을 쓰면 최대값 후보를 빠르게 볼 수 있지만, 힙 안에 이미 윈도우 밖으로 나간 값이 남아 있을 수 있습니다. 그래서 top을 볼 때마다 오래된 인덱스를 lazy deletion으로 정리해야 합니다.
덱은 애초에 순서를 유지하며 앞에서 오래된 값만 버리기 때문에 이 문제가 더 단순합니다. cp-algorithms의 minimum queue 설명도 같은 계열의 아이디어를 다룹니다.
Python 구현
from collections import deque
def max_sliding_window(nums, k):
dq = deque() # index만 저장한다
answer = []
for i, x in enumerate(nums):
while dq and dq[0] <= i - k:
dq.popleft()
while dq and nums[dq[-1]] <= x:
dq.pop()
dq.append(i)
if i >= k - 1:
answer.append(nums[dq[0]])
return answer이 코드에서 덱의 앞은 현재 최댓값 후보입니다. 뒤에서는 새 값보다 약한 후보를 제거합니다. 그래서 전체 시간 복잡도는 O(n)입니다.
언제 이 풀이를 떠올릴까
- 고정 길이 구간이 움직인다.
- 각 구간의 최댓값 또는 최솟값을 묻는다.
- 구간 안의 값이 들어오고 나가는 순서가 중요하다.
- 힙으로 풀면 오래된 값 제거가 번거롭게 느껴진다.
이 감각은 큐를 쓰는 위상 정렬 글처럼 자료구조가 문제의 흐름을 어떻게 줄여주는지 보는 연습과도 연결됩니다.
정리
슬라이딩 윈도우 최댓값에서 덱은 모든 값을 저장하는 창고가 아닙니다. 현재와 미래의 최댓값 후보만 남기는 필터입니다. 이 관점만 잡으면 구현 순서도 훨씬 자연스러워집니다.
