문제
https://www.acmicpc.net/problem/11286
11286번: 절댓값 힙
첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0
www.acmicpc.net
풀이
from queue import PriorityQueue
import sys
input = sys.stdin.readline
n = int(input())
queue = PriorityQueue()
for i in range(n):
request = int(input())
if request == 0:
if queue.empty():
print('0')
else:
temp = queue.get()
print(str((temp[1])))
else:
queue.put((abs(request), request))
설명
- 우선순위 큐 에 대해 인지하지 못했다.
우선순위 큐=pop을 할 때 먼저 들어온 원소가 나오는 대신 우선순위가 가장 높은 원소가 나오는 큐
1. 원소의 추가가 O(lg N)
2. 우선순위가 가장 높은 원소의 확인이 O(1)
3. 우선순위가 가장 높은 원소의 제거가 O(lg N)
'Coding Test > Python' 카테고리의 다른 글
| [백준] ABCDE (0) | 2023.07.25 |
|---|---|
| [백준] 연결 요소의 개수 (0) | 2023.07.17 |
| [백준] 카드2 (0) | 2023.07.05 |
| [백준] 오큰수 (1) | 2023.07.05 |
| [백준] 최솟값 찾기 (0) | 2023.07.03 |