5장) 슬라이딩 윈도우 실전문제(백준 11003번)

예제 입력 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

---

# 조건

• N개의 수와 L이 주어짐
• A_i-L+1 ~ A_i 중 최솟값을 D_i 라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하라.
  (단, i<=0인 A_i는 무시하고 D를 구해라)

# 예제 입력

 

# 문제분석하기

1. 최대 크기가 5,000,000이므로, 정렬 사용시 Timeout 발생.

 → 덱(deque)으로 구현 필요

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

 

2. 아주 중요한 핵심 개념 2가지

1. 최솟값 가능성이 없는 데이터 삭제(빨강)
2. window 크기 밖 데이터 삭제(파랑)

---

# 실제 예시

---

# 슈도코드 작성

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

for N만큼 반복: # now 리스트를 탐색하며 now[i]를 현재 값으로 세팅
   덱의 마지막 위치에서부터 현재값보다 큰 값을 덱에서 제거 # 1번 아이디어(최솟값 유지)
   덱의 마지막 위치에 현재값과 현재 인덱스를 함께 저장
   [덱의 1번째 위치에 있는 데이터의 인덱스 <= 현재 인덱스 - L] 이면 덱에서 제거 # 2번 아이디어(window 넘어간 값 제거)
   덱의 1번째 데이터 값을 출력

 

---

 

# 정답 코드 작성

from collections import deque
import sys

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

for i in range(N):
    # 아이디어1: 나보다 큰 데이터 삭제
    while mydeque and mydeque[-1][0] > now[i]:
        mydeque.pop()

    mydeque.append((now[i], i))

    # 아이디어2: 슬라이딩 윈도우 벗어난 데이터 삭제
    if mydeque[0][1] <= i-L: # 범위에서 윈도우 범위를 벗어나는 경우
        mydeque.popleft() # 앞에서 빼는경우 popleft()
    
    print(mydeque[0][0], end=' ')