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

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

11003번: 최솟값 찾기

 

1. 난이도 플레티넘 5

 

이 문제의 데이터의 범위는 0 ~ 5,000,000이기 때문에 정렬(O(nlogn))을 이용해서 풀면 시간초과가 발생한다.

 

따라서 deque를 이용해 정렬을 진행해야한다.

 

 

문제를 해결하는 알고리즘은

 

1. deque의 마지막에 있는 값들부터 현재 들어올 값보다 크면 최솟값이 아니기 때문에 모두 pop을 시킨다.

 

2. dequq의 마지막에 현재 값과 인덱스를 함께 저장한다.

 

3. deque의 제일 앞에 있는 값이 L의 범위를 넘어가면 popleft 시킨다.

 

4. dequq의 첫 번째 데이터를 출력한다.

 

 

2. 내가 작성한 코드

from collections import deque

n,l = map(int, input().split()) #n=숫자의 개수 l = 범위
num = list(map(int, input().split()))

entity = deque()

for i in range(n):
  while entity and entity[-1][0] > num[i]:
    entity.pop()
  entity.append((num[i],i))

  if entity[0][1] <= i-l:
    entity.popleft()
  print(entity[0][0],end=" ")