문제

11003 - 최솟값 찾기

접근

슬라이딩 윈도우를 하며 탐색해야 한다.

처음에는 힙(우선순위큐)을 이용하여 문제를 풀었다.

힙에 배열의 값과 인덱스를 저장하고, 배열의 값을 이용해서 힙을 구성한다.

원소를 순서대로 보면서 힙에 넣고, 힙에 최소값이 슬라이딩 구간을 벗어나면 힙에서 제거하는 식으로 풀었다.

힙에서 원소를 추가하거나 제거할 때 힙을 재구성하는 데 로그 n의 시간이 걸린다.

이 때문에 시간초과가 난거같다.. 힙보다 빠르게 연산을 수행해야 한다.

한참 생각해보니 굳이 최소값을 계속 갱신해주며 힙을 유지할 필요가 있나 싶었다.

결국 특정 새로운 원소가 추가될 때 이 원소보다 큰 값은 유지될 필요가 없다.

인덱스로 볼 때에도 새로 추가되는 원소가 가장 오래 남을 테니!

덱으로 구성하고 덱의 앞에 항상 최소값이 오도록해보자

삽입은 항상 뒤에 할 것이다.

삽입할 요소도 값과 인덱스 두개로 똑같다.

삽입하기전에 덱을 뒤에서 부터 보며 삽입하려는 요소보다 큰값을 모두 빼준다.

이렇게 하고 삽입한다면 덱은 항상 오름차순으로 정렬된 상태를 자동적으로 유지할 것이다.

추가적으로 슬라이딩 범위를 벗어난 요소들을 생각해주어야 한다.

이는 삽입하기전에 덱을 앞에서부터 보며 인덱스 범위가 벗어난 요소들을 빼준다.

순서는

1. 뒤에서부터 확인하며 삽입하려는 요소보다 큰 값들을 제거
2. 앞에서부터 보며 슬라이딩 범위를 벗어난 요소들을 제거
3. 현재 요소 삽입

모든 연산은 상수시간 O(1)로 해결이 가능하다.

즉 전체 배열을 확인하는데 O(n)이면 된다.

코드

• 파이썬 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

from collections import deque
import sys

input = sys.stdin.readline

n, k = map(int, input().split(' '))

arr = list(map(int, input().split(' ')))
q = deque()
ans = []
for i in range(n):
    while q and q[-1][0] > arr[i]:
        q.pop()
    while q and q[0][1] < i - k + 1:
        q.popleft()
    q.append((arr[i],i))
    print(q[0][0], end = ' ')