[BOJ/PYTHON] 11003. 최솟값 찾기

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

문제 요약

본인 포함 본인부터 본인 기준 L번째 왼쪽(Ai-L+1 ~ A)까지 중 최솟값 리스트 출력

핵심 아이디어

슬라이딩 윈도우를 사용한다!

문제 자체는 플래티넘 수준이 아니지만 시간초과 기준 때문에 플래티넘 문제가 된 것 같다.

덱을 이용할 경우 인덱스 정보를 저장하는 게 핵심인데, 봐야 할 범위의 최소 인덱스보다 더 작은 인덱스가 남아있으면 볼 필요가 없으니까 버리면 된다.

그리고 while을 이용해 이번에 들어올 수보다 더 큰 수가 큐에 남아있다면 다 버린다. 최솟값을 찾는 거라 큰 수는 큐에 남아있을 필요가 없기 때문이다.

각 맨 앞에 있는 값을 출력하면 된다.

풀이

# platinum5-11003. 최솟값 찾기

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

n, l = map(int, input().split())
array = list(map(int, input().split()))

# 슬라이딩 윈도우로 L 범위만큼만 이동

q = deque()
for i in range(n):
    if q and i - l + 1 > q[0][0] : q.popleft() # 봐야 할 범위의 최소 인덱스보다 작은 인덱스가 남아있으면 버림
    while q and q[-1][1] > array[i]: # 큰 수 버리기
        q.pop()
    q.append((i, array[i]))
    print(q[0][1], end=' ')

Trouble Shooting

• min을 이용하는 방법 → 시간초과
• for num in array: if len(q) >= l: q.popleft() q.append(num) print(min(q), end=' ')

실행 시간

메모리 756304KB, 시간 7712ms (python3)