[BOJ] 11003 - 최솟값 찾기 (Python)

 

 

아이디어

 

덱을 이용하여 범위 내에서의 최솟값을 찾는다.

 

 

풀이

 

for문에서 현재 값이 덱 queue에서 가장 작은 값이 되도록 현재 값보다 큰 값들은 pop하여 없앤다.

범위를 벗어나는 값들은 popleft로 제거하는데, pop하여 남아 있지 않은 값이 있을 수 있으므로 A의 해당 값과 비교한다.

res에 queue의 맨 앞에 있는 값을 문자열로 추가한 후, join 메서드로 공백으로 구분한 결과값을 출력한다.

 

from collections import deque

def solution():
    N, L = map(int, input().split())
    A = tuple(map(int, input().split()))
    queue = deque()
    res = []
    for i in range(N):
        while queue and queue[-1] > A[i]:
            queue.pop()
        queue.append(A[i])
        if i >= L and queue[0] == A[i-L]:
            queue.popleft()
        res.append(f'{queue[0]}')
    print(' '.join(res))

solution()