문제 분석
주어진 정수 배열에서 한칸씩 이동하면서 특정 길이만큼의 구간에서 최솟값을 찾는 문제이다. 수업때 CUDA 프로그래밍에 대해 배우면서 접했던 stencil과 같은 모양을 하고있어서 금방 이해가 되었다. 찾아보니 슬라이딩 윈도우라는 이름으로 불리는 것 같다.
처음에는 문제에서 제시한대로 전체 정수배열을 돌면서 주어진 범위에서 최솟값을 구하기 위해 큐의 front를 pop하고 새로운 원소를 추가한 다음 최솟값을 갱신했다. 그런데 파이썬에서 min()의 시간복잡도는 O(n)이기 때문에 이 방법으로는 시간초과가 발생한다.
그래서 이번에는 힙을 이용해서 전체 정수배열을 돌면서 새로운 원소를 push하면 자동으로 최솟값이 나오도록 구현했다. 그런데 구간을 이동하면서 front의 값을 힙에서 제거해주어야 하는데 이 때에도 별다른 방법이 떠오르지 않아 remove()를 사용했더니 역시 시간초과가 발생했다.(remove()의 시간복잡도도 O(n))
결국 O(n^2)보다 적은 시간 안에 해결해야 하는데, 최솟값을 갱신하는 부분에서 막혀 풀이를 찾아보았다.
Key Idea
이 문제는 덱과 힙 두 가지 자료구조를 사용해서 문제를 풀 수 있는데, 공통적으로 사용되는 아이디어는 인덱스를 사용하여 최솟값이 유효한지 검사하는 것이다.
deque
덱은 큐의 맨 앞과 맨 뒤에서 push, pop이 가능하기 때문에 이를 이용하여 최솟값을 오름차순으로 정렬한다. 즉, 큐의 front에는 항상 최솟값이 올 수 있도록 하고, 새로운 원소가 최솟값보다 작으면 덱의 앞에 추가한다. 만약 그렇지 않다면 덱의 뒤에 추가하는데, 이때 큐에서 자신보다 큰 원소는 모두 pop한다.
이게 가능한 이유는 큐에 들어있는 정수들은 이미 구간 안에 포함되어있는 숫자들인데, 새로운 원소가 이들보다 작으면 자연스럽게 큐에 있는 정수들이 포함된 구간에서는 자신이 최솟값이 될 수 없기 때문이다.
예를 들면 [1,4,2,3,5] 가 주어져있고, 구간의 길이가 3일 때, 2를 확인하는 시점에서 4는 더이상 최솟값이 될 수 없으므로 덱에서 제거해도 된다.
이후 덱의 front를 결과에 추가하는데, 이때 이 최솟값이 구간 안에 있는 정수인지 검증하기 위해 덱에 정수값과 함께 인덱스를 넣고, 인덱스를 확인하여 구간 안에 포함된 최솟값만 결과에 추가한다.
heap
최소힙을 사용하면 구현이 조금 더 간단하다.
최소힙은 root에 항상 최솟값이 보관되기 때문에 전체 배열을 돌면서 힙에 원소를 추가한 다음 힙의 root를 확인하면 된다. 이때에도 최솟값이 구간 안에 포함되는지 검증하기 위해 힙에 원소를 추가할 때 인덱스를 같이 넣고, 힙의 root가 구간 안에 포함된 값인지 확인한 다음 결과로 추가한다.
Solution
위의 아이디어들을 코드로 구현한 것이다. 코드 수는 덱을 이용한 방법이 더 길지만 실행시간은 덱을 사용했을 때 조금 더 짧았다.
deque
n, l = tuple(map(int, sys.stdin.readline().strip().split(" ")))
a = list(map(int, sys.stdin.readline().strip().split(" ")))
d = [a[0]]
q = deque([(a[0], 0)])
for i in range(1, n):
if a[i] <= q[0][0]:
q.appendleft((a[i], i))
else:
while a[i] < q[-1][0]:
q.pop()
q.append((a[i], i))
while i - l + 1 > q[0][1]:
q.popleft()
d.append(q[0][0])
for i in d:
print(i, end=" ")heap
최솟값이나 최댓값을 유지/갱신해야 하는 문제가 나오면 힙이 최고인 것 같다.
n, l = tuple(map(int, sys.stdin.readline().strip().split(" ")))
a = list(map(int, sys.stdin.readline().strip().split(" ")))
d = []
h = []
for i in range(n):
heapq.heappush(h, (a[i], i))
while h[0][1] < i - l + 1:
heapq.heappop(h)
d.append(h[0][0])
for i in d:
print(i, end=" ")