반응형
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=' ')
근데 플레티넘 문제가 이게 진짜 정해라고..?
반응형
'알고리즘 문제 > BOJ (Python3, C++)' 카테고리의 다른 글
[백준] 13549 - 숨바꼭질 3 (BFS 풀이) (0) | 2024.10.01 |
---|---|
[백준] 19663 - Mountains (0) | 2024.07.26 |
[백준] 1600 - 말이 되고픈 원숭이 (Python) (2) | 2024.07.14 |
[백준] 11780 - 플로이드 2 (Python) (2) | 2024.07.07 |
[백준] 21606 - 아침 산책 (Python) (2) | 2024.07.05 |