[백준 11003번] 최솟값 찾기 (Python3)

from collections import *

N,L = map(int,input().split())
seq = [*map(int,input().split())]

dq = deque()
for i in range(N):
  x = seq[i]
  while dq:
    if dq[0][1]<=i-L:
      dq.popleft()
    elif dq[-1][0]>=x:
      dq.pop()
    else:
      break
  dq.append((x,i))
  print(dq[0][0],end=" ")

이전의 최솟값 찾기 [백준 11003번] 최솟값 찾기 (Python3) (tistory.com) 문제를 시간복잡도 O(NlogN)에 해결하였었는데, O(N)으로 개선한 코드이다.

pypy로만 제출되었던 기존의 풀이와 다르게 python으로도 제출할 수 있었고, pypy에서도 제출시간이 크게 개선되었다.

 

풀이를 설명하면,

1. deque를 이용한다. dq에는 항상 오름차순으로 값과 인덱스를 포함한 튜플이 배치되며, dq[0][0]가 곧 출력해야하는 값이다.

2. deque[0]의 인덱스값이 범위를 벗어나는 경우 popleft를 한다.

3. deque[-1]의 값이 현재 입력할 값보다 작은 경우 pop한다.

4. deque에 (현재 값, index)를 튜플로 삽입한다.

5. deque[0]의 값을 출력한다.

 

스택에 값과 인덱스를 튜플로 삽입하는 것을 통해 결과를 구한다는 점에서 [백준 6549번] 히스토그램에서 가장 큰 직사각형 (Python3) (tistory.com) 의 풀이와 유사한 부분이 있었다.

 

오늘의 교훈) 스택을 적절하게 활용하자.