문제 링크

바로가기

문제 풀이

PY

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

N, L = map(int, input().split())
numbers = list(map(int, input().split()))
window = deque()

for (i, num) in enumerate(numbers):
  while window and window[-1][1] > num:
    window.pop()
  window.append((i, num))
  if window[0][0] < i - L + 1: window.popleft()
  print(window[0][1], end=' ')

풀이

범위가 엄청 크면서 배열 안의 부분을 이동하면서 체크해야할 때는 슬라이딩 윈도우를 사용하는 것이 적합하다.

12 3
1 5 2 3 6 2 3 7 3 5 2 6

이렇게 입력을 받았을 때,

[1]
[1, 5]
[1, 5, 2]
[5, 2, 3]

이런 식으로 범위를 정한 다음에 최솟값을 구해야한다. 다만, 배열의 길이와 슬라이딩 배열의 최대 크기가 5000000이기 때문에 순회하면서 또 최솟값을 구하고 하기에는 무리가 있다.

슬라이딩 윈도우를 사용하면 최솟값을 구하는 반복을 최소화할 수 있다.
해당 부분에서 처음으로 deque를 사용했다.
일반적인 리스트의 pop(0)과 deque의 popleft은 성능차이가 있기 때문이다.

먼저 입력 받은 숫자들을 순회하면서 덱의 끝 숫자와 넣을 숫자를 비교해주고, 덱의 끝 숫자가 더 크면 pop을 한다.

그런 다음에 덱에 숫자를 넣어준다. 이때 인덱스와 함께 튜플의 형태로 넣어주는데 슬라이딩 윈도우의 범위를 가져야하기 때문에 덱의 맨 앞 원소의 인덱스를 검사해주고 범위를 벗어나면 popleft 해주어야 하기 때문이다.

이러한 과정을 거치면서 계속 덱의 맨 앞 원소의 값을 출력해주면 최솟값을 쉽게 찾을 수 있다.

새롭게 배운 점

1. 덱을 임포트 할 때 from collections import deque
2. window = deque()
3. popleft, appendleft는 모두 시간 복잡도가 O(1)이다.