최소값 찾기 (deque 문제)

https://www.acmicpc.net/problem/11003

문제

N개의 수 A1, A2, ..., AN과 L이 주어진다.

Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

입력

첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000)

둘째 줄에는 N개의 수 Ai가 주어진다. (-109 ≤ Ai ≤ 109)

출력

첫째 줄에 Di를 공백으로 구분하여 순서대로 출력한다.

예제 입력

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

예제 출력

1 1 1 2 2 2 2 2 3 3 2 2

풀이

슬라이딩 윈도우 문제다. 이런 문제의 경우에는 대부분 시간초과에 걸릴 확률이 높아 단순히 loop을 돌리면서 그때마다 최소값을 구하면 시간복잡도 문제를 해결하지 못할 가능성이 높다. deque(덱) 을 사용하면 복잡도 문제 없이 풀 수 있는데, 처음에는 그냥 pop(), pop(0) 을 활용해 list로 풀었지만 deque와 list의 시간복잡도에 차이가 있다고 해서 deque로 풀었다.

기본적으로 deque와 list의 pop은 O(1)이지만 pop(0)의 복잡도가 다르다. Deque은 O(1)인데 list은 O(n)이다.

n = 1,000,000 일 때, deque.popleft()은 0.098, list.pop(0)은 372.62이다. 어마어마한 차이다.

이 문제를 풀기 위해서 조금 유연하게 생각할 필요가 있다. 슬라이딩 윈도우기 때문에 숫자가 하나씩 들어올텐데, 숫자가 들어올 때마다 앞에 있는 수를 제거해주면 된다. 그리고 윈도우 왼쪽에 있는 숫자를 매번 지워나가야 하는데, 해당 숫자가 있을 때만 지우면 된다. 예를들어 보자.

[8, 6, 4, 2, 3, 4, 5, 1]의 배열이 있고 윈도우 크기가 4이다. 문제를 보면 [8, 6, 4, 8]부터 시작하게 되어있지 않고, 그냥 [8]부터 시작하되 앞에 숫자가 없는 상황이므로 [None, None, None, 8]부터 시작하는 것과 같다.

[8]

8이 가장 작은 수이므로 8을 그냥 print하면 된다. 다음 수는 6인데, 8하고 6 중에서 6이 더 작으므로 앞에 있는 수를 지운다. 따지고 보면 [None, None, 8, 6]이 되는 셈이다.

[6]

다음 수는 4이므로 같은 방식으로 6이 지워진다. 그리고 2까지가면 2만 남을 것이다.

[2]

다음에 오는 수는 3이다. 3은 2보다 크므로 그냥 넣는다. 윈도우는 사실 [6, 4, 2, 3] 이다.

[2, 3]

다음에 오는 수는 4이고 역시 3보다 크므로 그대로 들어간다. 윈도우는 [4, 2, 3, 4] 인데, 최소값인 2가 가장 앞에 있다.

[2, 3, 4]

다음에 오는 수는 5이다.

[2, 3, 4, 5]

다음에 오는 수는 1이다. 5은 1보다 크므로 5를 빼준다. 그 앞에 있는 4도 1보다 크므로 4를 빼주고 3까지 빼준다. 그리고 윈도우의 크기는 4를 넘어갈 수 없다. 2가 빠져야할 차례이기 때문에 맨 앞의 2를 빼준다.

[1]

이와 같은 로직을 작성하려면 두가지 조건이 필요하다.

• 들어갈 숫자가 앞에 있는 수보다 큰 경우 모두 지워야 한다.
• 입력배열 [i-l] 번째 숫자가 배열의 맨 앞에 있는 숫자와 같으면 맨 앞에 있는 숫자를 지워야 한다. (윈도우 크기를 넘어가는 숫자는 지워져야 한다는 뜻)

이렇게 되면 매번 대소 비교를 하지 않아도 비교를 해야할 요소들을 다 지워버리기 때문에 O(N)에 가까운 복잡도를 갖게된다.

[8, 7, 6, 5, 4, 3, 2, 1]과 같이 작아지는 숫자가 엄청 많다고 하더라도 비교해야할 대상은 이미 앞에서 지워지기 때문에 복잡도가 줄어드는 것이다.

from collections import deque

n, l = map(int, input().split())
array = [*map(int, input().split())]

result = deque()

for i in range(n):
  now = array[i]

  # 앞에 있는 큰 숫자가 없을 때까지 삭제
  while result and result[-1] > now:
    result.pop()
  result.append(now)

  # 윈도우 크기를 넘어가는 경우 맨 앞에 있는 숫자 삭제
  if i >= l and result[0] == array[i-l]:
    result.popleft()

  print(result[0], end=' ')