[python] 백준 11003 최솟값 찾기

https://www.acmicpc.net/problem/11003

11003번: 최솟값 찾기

문제 해결

• i~i+l-1 까지 리스트 원소중 최솟값을 찾는 것이다.
• 다른 수들은 고려할 필요가 없으므로 (value,index)를 deque를 이용해 저장하자.
• 원소를 0~n까지 돌면서 deque[-1][0]과 비교하여 원소가 더 작으면 deque[-1][0]을 빼준다. 이를 반복한다. 필요 없기 때문에... 그리고 deque[-1][0]이 더 커지는 때가 오면 오른쪽에 그 원소를 넣는다.
• 만약 deque[-1][0]이 더 크면 원소를 deque오른쪽 자리에 넣는다. 이는 i~i+l-1까지 원소 중 최솟값을 구하는 것이므로 혹시모를 예비 순번을 생각하면 되는 것이다.
• 원소를 돌면서 바로바로 출력을 할 것이다. i번째 원소를 돌고있으면 i-l+1~i-l번째 원소를 관찰한다고 보면 된다. 이는 코드를 보면 알겠지만 i-l+1이 음수여도 상관이 없다,
• 만약 deque의 맨 왼족 원소가 그 범위안에 들어가지 않으면, 즉 i-l+1보다 작으면 popleft()를 통해 버려준다. 유통기한이 지났다고 생각하면 된다.
• 마지막에 남은 deque의 맨 왼쪽 수를 출력한다. 이때 아직 i번째 돌고 있으므로 end=' '를 통해 출력을 이어나갈 것이다.

CODE

import sys
from collections import deque
input = sys.stdin.readline

n, l = map(int, input().split())
que = deque()
A = list(map(int, input().split()))

for i in range(n):
    while que and que[-1][0] > A[i]:
        que.pop()
    que.append((A[i], i))
    if que[0][1] <= i-l:
        que.popleft()
    print(que[0][0], end=' ')