[백준/BOJ] platinum5 - 11003번 최솟값 찾기 (Python)

▶11003 - 최솟값 찾기

▶문제

N개의 수 A1, A2,..., AN과 L이 주어진다.

Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

 

▶입력

첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000)

둘째 줄에는 N개의 수 Ai가 주어진다. (-109 ≤ Ai ≤ 109)

 

▶출력

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

728x90

 

▶풀이

deque를 이용해서 값을 구했다.

기존에 deque에 존재하는 값이 새로 들어오는 값보다 큰 경우에는 그냥 빼주었다.

그다음에 index와 그 arr값을 넣어주었다.

 

만약에 새로운 값이 들어왔는데 가장 앞에 있는 값과의 차이가 L보다 크거나 같으면, 그 값도 제거해주어야 한다.

L만큼만 비교를 하면 되기 때문이다.

from collections import deque

n, l = map(int, input().split())
arr = list(map(int, input().split()))
result = [0 for _ in range(n)]
check = deque()
for i in range(n):
    while check and check[-1][1] > arr[i]:
        check.pop()
    check.append((i, arr[i]))
    if i >= check[0][0] + l:
        check.popleft()
    result[i] = check[0][1]

for re in result:
    print(re, end=' ')