[백준 11003번] 최솟값 찾기 (Python/파이썬)

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

11003번: 최솟값 찾기

문제를 처음 보고 떠올린 것은 최솟값을 구해야 하는 구간에서 정렬하거나 min()함수를 이용하는 방법인데 시간초과 날것이 뻔했다

(파이썬에서 sort()의 시간복잡도는 O(NlogN)이다)

그래서 배열을 훑으면서 바로바로 최솟값을 찾아내야겠다고 생각했다. 슬라이딩 윈도우와 큐, 스택을 활용하여 최솟값을 구하였다.

 

 

2

1

5

4

2

6

위의 숫자들에서 최솟값을 구해야하는 범위가 3이라면, 일단 스택에 첫번째 숫자를 추가

2

다음으로 들어올 숫자가 1인데 원래 있던 숫자보다 작으므로 2 삭제하고 1 추가

1

5가 들어와야하는데 1보다 크므로 그대로 대입

1

5

4가 들어와야하는데 전 숫자인 5보다 작으므로 5 삭제

1

4

슬라이딩 윈도우의 크기가 3이므로 앞에 1삭제, 다음으로 들어올 숫자가 2인데 4보다 작으므로 4 삭제

2

배열의 첫번째 원소가 최솟값이 된다.(2, 1, 1, 1, 2, ...)

이런 식으로 계속 들어올 숫자가 마지막 숫자보다 작으면 원래 있던 숫자는 삭제하고, 슬라이딩 윈도우 범위에 안맞는 숫자도 삭제하는  방식을 반복하다보면 배열을 한번만 훑으면서도 최솟값을 찾아낼 수 있다.

정렬이나 min() 함수를 사용하지 않고도 스택과 큐를 사용하여 최솟값을 찾아낸다.

코드는 다음과같다.

튜플을 활용하여 (인덱스, 숫자)를 deque에 넣었다.

입력 예시를 손으로 직접 해보면 이해가 쉬울 것이다.(이 문제 뿐 아니라 손으로 한번 써보는게 도움이 많이 된다.)

 

import sys
from collections import deque
input = sys.stdin.readline
N, L = map(int,input().split())
num = list(map(int, input().split()))
##최솟값을 구할 곳
temp = deque([])

for i in range(N):
  ## 슬라이딩 윈도우 범위를 벗어나는 원소 삭제(당연히 맨 앞의 원소)
  if temp and temp[0][0] <= i-L:
    temp.popleft()

  ## 들어올 원소가 기존의 원소보다 작으면 기존원소 삭제
  while len(temp) >= 1 and num[i] < temp[-1][1]:
    temp.pop()

  ## 들어올 원소 추가
  temp.append((i,num[i]))
  
  print(temp[0][1], end = " ")

 

처음에는  deque()를 사용하지 않고 리스트로 했다가 시간초과가 나서 바꾸었다.

 

글에대한 조언, 질문 모두 환영합니다.