[11003]최솟값 찾기1

슬라이딩 윈도우

• 2개의 포인터로 범위를 지정한 다음, 범위(window)를 유지한 채로 이동(sliding)하며 문제 해결

슬라이딩 윈도우를 덱(deque)으로 구현

시간 복잡도 때문에 정렬을 사용할 수 없다. O(n)의 시간 복잡도로 해결해야함.
그래서 슬라이딩 윈도우롤 덱으로 구현하여 정렬 효과를 본다.

덱의 구조

• 덱은 큐랑 비슷하게 양 끝에서 데이터 삽입 삭제가 가능하다.
• 덱에서는 (인덱스, 숫자) 형태의 노드를 클래스로 구현하여 저장
  

최솟값 가능성 없는 데이터 삭제

• 1, 5가 존재하는 상태에서 2가 새로 들어왔고 뒤에서부터 비교를 한다.
• 뒤에서부터 2와 5를 비교했을 때, 5의 노드는 최솟값이 될 가능성이 없으니 (2, 5) 노드를 제거한다.
  

window 크기 밖 데이터 삭제

• L을 넘어가는 데이터는 볼 필요가 없으므로 제거해야함.
• 현재 인덱스 값 4내에서 L(=3) 범위는 2, 3, 4이다.
• 그러므로 현재 남아 있는 (1, 1)노드는 덱에서 제거해야한다.
• 4(마지막 데이터 index) - 3(슬라이딩 윈도우 크기) >= 1 이므로 맨 앞 데이터는 슬라이딩 윈도우 크기를 벗어나 삭제
  

# N: 데이터 개수, L: 최솟값을 구하는 범위
# mydeque: 데이터를 담을 덱 자료구조
# now: 주어진 숫자 데이터를 가지는 리스트

from collections import deque

N, L = map(int, input().split())
mydeque = deque()
now = list(map(int, input().split()))

for i in range(N):
    # 아이디어1. 나보다 큰 데이터 삭제하기
    # mydeque에서 (값, 인덱스) 형태로 저장
    # 인덱스 -1: 뒤에서 첫 번째(가장 마지막) 요소

    # mydeque에 데이터가 있을 때 까지 & 제일 끝에 있는 값과 현재 리스트 값과 비교해서
    while mydeque and mydeque[-1][0] > now[i]:
        mydeque.pop()
    
    # 덱의 마지막 위치에 현재 값 저장
    mydeque.append((now[i], i))

    # 아이디어2. 슬라이딩 윈도우 벗어난 데이터 삭제
    if mydeque[0][1] <= i-L:  # 윈도우 범위를 벗어나면
        mydeque.popleft() # 덱의 1번째 데이터 출력

    print(mydeque[0][0], end=' ')

남아 있는 mydeque의 형태가 궁금해서 출력해봤더니

deque([(2, 10), (6, 11)])

로 출력되었다.
mydeque에서는 (값, 인덱스)로 설정되어 있었고, 책의 설명된 것보다 '-1'된 인덱스 값이 들어있었다.