[11003] 최솟값 찾기 #파이썬

	백준 문제풀이		python
			No. 11003 최솟값 찾기

 

 

#파이썬 #백준 #문제풀이 #11003 최솟값 찾기

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

11003번: 최솟값 찾기

 

 

이번 글에서는 슬라이드 윈도우와 deque를 이해하는데 중점을 둔다.

예제 입력1

12 3
1 5 2 3 6 2 3 7 3 5 2 6

예제 출력1

1 1 1 2 2 2 2 2 3 3 2 2

 

---

// 알고리즘

가장 중요한 목적이 무엇인지?

슬라이드 윈도우 형식으로 3에 해당하는 묶음에서 최솟값을 찾는 문제이다.

queue를 사용하면 슬라이드 윈도우를 구현할 수 있는데, 문제는 최솟값이라는 점. 큐 내에서 정렬을 해야하고 pop()을 사용하고 싶으면 내림차순으로 정렬해야할 것이다.

아예 보기좋게 deque를 사용하면 popleft()로 최솟값을 뽑아낼 수 있다.

 

왜 이런 방법을 선택했는지?

5,000,000 이라 nlogn 정렬을 사용하면 2.4초 이상의 시간이 걸릴 수 있다.

 

---

// 계획하기

	함수명	설명
1.
2.
3.

 

---

// 구현하기

-> How?

어떻게 구현?

 

deque를 사용하는 방법을 먼저 학습해야한다.

덱의 구조를 보면 양끝에서 데이터를 삽입하고 삭제할 수 있는 자료구조이다.

왼쪽은 appendleft(), popleft() 함수가 삽입, 삭제 역할을하고 오른쪽에선 append() pop()이 삽입, 삭제를 한다.

 

 

 

 

덱에서는 (인덱스, 숫자) 형태의 노드를 클래스로 구현하여 저장하기 때문에, 인덱스가 ~3의 범위를 유지하면서 최솟값을 유지하면 된다.

 

 

예제 코드를 보면

12 3
1 5 2 3 6 2 3 7 3 5 2 6

(1,1) (2,5) (3,2) 값이 deque에 들어갈때 정렬을 하는 방법은 해당 값이 작다면 앞의 값을 지우는 것이다. 즉 들어오는 수가 앞의 수 보다 크면, 넣는다.

 

따라서 (1,1) (2,5) (3,2) 에서 3,2이 들어왔을때 앞의 5보다 작으니 앞의 값을 지운다. 그리고 1보다는 크니 넣는다.

(1,1) (3,2) 으로 1,2,3의 인덱스범위로 window:3을 유지하니 이 크기에서 최솟값은 1이다.

(1,1) (3,2) (4,3)이 들어오면 인덱스가 넘어가니 (1,1)을 지운다. 맨 뒤 인덱스(4)에 맞추면 된다.

(3,2) (4,3) (5,6)

(4,3) (5,6) (6,2)

(6,2) (7,3)

(6,2) (7,3) (8,7)

...

 

from collections import deque
mydeque = deque()

->Why?

왜 이런 방법을?

 

N에 관한 시간복잡도와 관련이 깊다.

 

---

// 수정하기

 

 

---

// 완성코드

#11003
import sys
input = sys.stdin.readline

from collections import deque
mydeque = deque()

N, L = map(int,input().split())
lists = list(map(int,input().split()))


for i in range(N):
    while mydeque and mydeque[-1][0] > lists[i]:
        mydeque.pop()
    mydeque.append((lists[i],i))
    if mydeque[0][1]<= i-L:
        mydeque.popleft()
    print(mydeque[0][0],end=" ")