[백준] 최솟값 찾기

문제

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

11003번: 최솟값 찾기

---

풀이

from collections import deque

n, l = map(int, input().split())
mydeque = deque()
now = list(map(int, input().split()))   # 주어진 숫자 데이터를 가지는 리스트

for i in range(n):
    while mydeque and mydeque[-1][0] > now[i]:
        mydeque.pop()
    mydeque.append((now[i], i))
    if mydeque[0][1] <= i-l:
        mydeque.popleft()
    print(mydeque[0][0], end=' ')

 

---

설명

- deque: 큐의 앞, 뒤에서 삽입, 삭제가 가능한 큐

- from collections import deque 선언을 해야 사용 가능!

 

<알고리즘 설명 - 노드를 제거하는 과정만 설명>

1. deque 에서는 (인덱스, 숫자) 형태의 노드를 클래스로 구현하여 저장한다. 

2. [1,1], [2,5] 가 저장되어 있는 상태에서 새 노드 [3,2] 가 deque 에 저장된다. 새 노드 [3,2]가 저장될 때 deque 뒤에서부터 비교를 시작한다. [2,5]는 [3,2]보다 숫자가 크므로 [2,5]는 deque에서 제거(pop) 된다. 이어서 [1,1] 은 [3,2] 보다 숫자가 작으므로 탐색을 멈추고 [3,2]를 deque에 저장(append) 한다. 결과를 보면 [2,5]가 deque에서 제거되어 deque에는 [1,1], [3,2] 순서로 노드가 오름차순 정렬되어 있다. 여기서 최솟값은 deque 처음에 있는 [1,1] 노드와 숫잣값 이다.

3. [1,1], [3,2] 가 저장된 노드에 [4,3] 을 추가해보자. 여기서는 인덱스 범위가 슬라이딩 윈도우를 벗어난 예를 알 수 있다.

새 노드 [4,3] 은 deque 뒤에서부터 비교했을 때 [3,2] 보다 숫자가 크므로 deque에 저장된다. 여기서 인덱스 범위에 의해 deque 앞쪽의 노드가 제거 된다. [1,1], [3,2], [4,3]의 인덱스 범윈느 1~4이므로 윈도우 범위인 3을 벗어난다. 최솟값은 윈도우 범위 내에서 찾기로 했으므로 [1,1]은 deque에서 제거 되야 한다. 제거가 끝난 이후에 최솟값을 출력하면 2 이다.

 

 

<사용 함수들>

append(x): 큐의 뒤로 삽입

appendleft(x): 큐의 앞으로 삽입

clear: 큐의 모든 요소 삭제

insert(i,x): i위치에 x를 삽입

pop(): 큐의 맨 오른쪽의 element 삭제 후 반환. element 없으면 IndexError 발생

popleft(): 큐의 맨 왼쪽의 element 삭제 후 반환. element 없으면 IndexError 발생

remove(value): 큐에 있는 value 값 중 처음으로 등장한 value 삭제. 못 찾으면 ValueError 발생

reverse(): 큐를 제자리에서 반대로 뒤집음