Sliding Window - (2)

최솟값 찾기 (백준 11003번, 시간 제한: 2.4초)

문제 예시
N개의 수 A1, A2, ..., AN과 L이 주어진다.
$D_i$= $A_{i-L+1}$ ~ $A_i$ 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 $A_i$는 무시하고 D를 구해야 한다.

입력
첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000)
둘째 줄에는 N개의 수 $A_i$가 주어진다. ($-10^9 ≤ A_i ≤ 10^9$)

출력
첫째 줄에 $D_i$를 공백으로 구분하여 순서대로 출력한다.

입력 예시
12 3
1 5 2 3 6 2 3 7 3 5 2 6

출력 예시
1 1 1 2 2 2 2 2 3 3 2 2

코드 예시

from collections import deque
import sys
input=sys.stdin.readline
n,l=map(int,input().split())
mydeqeue=deque()
arr=list(map(int,input().split()))
for i in range(n):
    while mydeqeue and mydeqeue[-1][0]>arr[i]:
        mydeqeue.pop()
    mydeqeue.append((arr[i],i))
    if mydeqeue[0][1]<=i-l:
        mydeqeue.popleft()
    print(mydeqeue[0][0],end=" ")

해당 문제는 input N,L이 각 5백만이기 때문에 sorting 시에 필요한 O(nlogn)이 아닌 O(n) 시간복잡도로 문제를 풀어야 하기 때문에 매우 어렵다.
이때 python 은 deque(덱) 자료구조를 지원하기 때문에 상대적으로 쉽게 풀 수 있다.
sorting을 O(n)으로 할 수 있다는 장점이 있다.

덱의 구조는
appendleft()<--------------> append()
popleft()<-----------------> pop()

이렇게 stack, queue 를 합쳐놓은 구조이다. 양방향으로 넣고 뺄 수 있는 장점이 있다.

그래서 해당 문제는 우선 첫번째 arr[i],i 두 노드를 덱에 넣는다.
이후 두번째 노드를 넣는데 그 전에, 가장 마지막 노드인 deque[-1][0] 과 arr[i]를 비교하여 arr[i]가 더 작으면 deqeue[-1]을 pop 한다.
우리는 가장 작은 값들만 원하기 때문에 필요 없는 노드이기 때문이다.
그 다음 해당 노드를 넣는다.
만약 deque[0][1] 즉 deque 의 가장 첫번째 노드의 Index가 i-l 보다 작거나 같다면 window를 벗어난 것 이기 때문에 해당 노드도 pop 해야 한다.

이 과정을 통해 deque[0][0]이 해당 window 에서 가장 작은 값인 것을 알 수 있다.

추가 설명

일반적으로 python 의 Print 가장 마지막은 개행문자로 끝이 난다.
이를 바꾸기 위해서는 end= 원하는 문자를 적으면 된다.
int, char 같은 서로 데이터타입이 다른 경우는 + 연산이 되지 않아 , 를 사용한다.

그리고 c언어와 달리 arr[-1] 처럼 음수 index인 경우 뒤에서부터 접근이 가능하다!!
2018년에 배웠더니 이런 사소한 것들이 기억나지 않는다..