[백준] 11003 - 최솟값 찾기 (Python, 우선순위 큐)

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

 

티어는 플레티넘 5인데, 우선순위 큐로 너무나도 간단히 풀리는 최강 날먹(?) 문제

질문 게시판을 보니, 덱을 이용해서 O(n) 에 풀 수 있도록 최적화 하는 것이 이 문제의 의도같은데, 입출력값이 너무 많아서 O(N) 으로 딱 제한을 두기가 힘든 모양이다..

 

그럼에도 불구하고 파이썬 시간 제한이 9초대도 통과되는 건 너무 봐준 것 아닌가 싶기도..

 

우선순위 큐 풀이는 최소힙에 (원소값, 원소 인덱스) 튜플을 저장하고, 범위가 늘어날 때마다 현재 보고 있는 원소를 우선순위 큐에 넣은 뒤, 최소힙에서 최소값을 본다.

만약 본 값이 현재 최소값을 찾는 범위에 있는 값이라면 출력하고, 아니라면 최소힙에서 빼는 과정을 반복한다.

 

결과적으로는 N번의 push, pop 만 일어나므로, O(n log n) 에 풀 수 있다.

 

from heapq import heappush, heappop
N, L = map(int, input().split())
nums = [0] + list(map(int, input().split()))
pq = []
for i in range(1, N+1):
    heappush(pq, (nums[i], i))
    value, index = pq[0]
    while 1 <= index < i - L + 1:
        heappop(pq)
        value, index = pq[0]
    print(value, end=' ')

 

근데 플레티넘 문제가 이게 진짜 정해라고..?