백준 - [Platinum 5] 11003번 최솟값 찾기

문제링크: https://www.acmicpc.net/problem/11003

11003번: 최솟값 찾기

---

문제 설명

- N: 숫자의 개수

- L: 임의의 수 

- Di = Ai-L+1 ~ Ai 중의 최솟값

ex)

N=12 L=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

 

i-L+1 <= 0 인 경우는 제외하고 계산한다.

---

풀이

Sliding Window를 활용한 문제입니다.

문제 난이도가 높게 설정된 이유는 입력의 범위와 음수가 들어갔기 때문이라고 생각합니다.

계속 min값을 구하게 되면 O(NlogN)의 시간복잡도가 나오게 됩니다. 또한 일반적인 list에서는 pop연산이 느리다.

그래서 deque와 sliding window를 활용하여 문제를 해결하여야 합니다.

 

1. i-L+1인덱스 이전인 것들은 queue에서 popleft한다.

2. 현재 들어오는 숫자보다 큰 숫자들은 queue에서 pop한다.

 

코드

from sys import stdin
from collections import deque
stdin = open("input.txt", "r")
# N: 숫자의 개수
# L: 임의의 수 
N, L = map(int, stdin.readline().split())

numbers = list(map(int, stdin.readline().split()))

queue = deque()

for i in range(N):
    # i-L+1 인덱스 이전인 것들을 pop해준다.
    while queue and queue[0][0] <= i-L:
        queue.popleft()

    # 들어갈 숫자보다 큰 것들은 전부 pop해준다.
    while queue and queue[-1][1] >= numbers[i]:
        queue.pop()

    queue.append((i, numbers[i]))
    print(queue[0][1], end=' ')