[백준 / Python] 11003번 최솟값 찾기

문제 

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

11003번: 최솟값 찾기

---

11003번 최솟값 찾기 파이썬 풀이

from collections import deque

N, L = map(int, input().split())
deque = deque()
data = list(map(int, input().split()))
for i in range(N):
    while deque and deque[-1][0] > data[i]:
        deque.pop() #계속 빼서 시간복잡도 줄이기 
    deque.append((data[i], i)) # 데이터, 인덱스
    if deque[0][1] <= i - L: #맨 앞에 범위 넘어선건 빼기
        deque.popleft()
    print(deque[0][0], end = ' ')

 

 

덱을 하나 만들고 입력받은 정수들을 리스트의 형태로 만듭니다. 

 

덱으로 정렬 효과를 보기위해 사전작업을 하고, 덱에 요소를 넣고, 후작업을 합니다. 

---

알고리즘

사전작업

먼저 요소를 넣기전, 

덱의 우측부터 입력받는 요소보다 정수가 큰 요소가 있는지 검사하며 있다면, 모두 제거합니다. (pop)

(이 작업으로 덱 안에서 오름차순으로 정렬이 되고, 동시에 비교할 정수가 적어져 연산 시간을 절약을 할 수 있습니다.)

 

요소 삽입

덱 우측에 요소를 삽입합니다. (append)

 

후작업

덱 좌측에 범위가 넘어선 요소가 있다면 제거합니다. 

 

위 알고리즘을 따르면 덱의 좌측에는 범위 L을 벗어나지 않고, 최솟값이 있으니, 덱의 가장 왼쪽 요소를 출력합니다. 

이를 N만큼 반복합니다. 

 

---