[백준] 11003번 최솟값 찾기 ★

💡문제접근

• 튜플을 활용하여 deque에 (원소값, 인덱스값)을 넣고 문제에서 요구하는 조건을 만족하는 경우를 따져 문제를 해결할 수 있었다. A는 deque로 하게 되면 시간초과가 발생하고 list로 하게 되면 시간초과가 발생하지 않았다. 그 이유는 명확히 알기가 어려워 관련 문서를 참조하여 공부했다.

파이썬 공식 문서 - deque

💡코드(메모리 : 754928KB, 시간 : 7740ms)

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

N, L = list(map(int, input().strip().split()))
A = deque(map(int, input().strip().split()))
D = deque()

for i in range(N):
    while D and D[-1][0] > A[i]:
        D.pop()
    while D and D[0][1] <= i - L:
        D.popleft()
    D.append((A[i], i))
    print(D[0][0], end = " ")

💡소요시간 : 1h