2022.02.17 [백준] (python 파이썬) 이중 우선순위 큐
https://www.acmicpc.net/problem/7662
7662번: 이중 우선순위 큐
입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적
www.acmicpc.net
풀이
https://neomindstd.github.io/%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4/boj7662/
[백준/파이썬] 7662번 이중 우선순위 큐 풀이
파이썬을 이용한 백준 온라인저지 문제풀이
neomindstd.github.io
이 문제는 위의 블로그의 설명을 보며 이해하고 풀었습니다.
이 문제는 최대힙과 최소힙 2개를 사용했다. 단순히 두개만 사용하면 데이터 동기화가 되지 않아 마지막엔 엉뚱한 값이 출력된다. 그래서 두 힙을 동기화 시키기 위해 for문의 순서를 각 힙에 식별자로 넣었다. 그래서 I로 힙에 넣을 땐 visited[i]를 True로 바꿔주었다. D가 입력 됬을 때, while문을 통해 각 힙에 False로되어있는 데이터는 이미 삭제 된 데이터이므로 삭제되지않은 데이터가 나올때까지 데이터를 버려준다.
그 다음 배열이 비어있으면 넘어가고 비어있지않으면 해당 식별자의 visited를 False로 바꾼뒤 루트노드를 버려준다.
모든 입력을 다 받고 난 후 역시 각 힙에 false로 되어있는 값들을 모두 버려준다.
이 후, 각 힙에 데이터가 들어있지않으면 EMPTY를 출력하고 들어있으면 각 힙의 0번째 인덱스를 출력해준다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
import heapq
import sys
input=sys.stdin.readline
for _ in range(int(input())):
min=[]
max=[]
visited=[False]*1_000_001
for i in range(int(input())):
s=input().split()
alpha=s[0]
num=int(s[1])
if alpha=='I':
heapq.heappush(min,(num,i))
heapq.heappush(max,(-num,i))
visited[i]=True
elif num==1:
while max and not visited[max[0][1]]:heapq.heappop(max)
if max:
visited[max[0][1]]=False
heapq.heappop(max)
else:
while min and not visited[min[0][1]]:heapq.heappop(min)
if min:
visited[min[0][1]]=False
heapq.heappop(min)
while max and not visited[max[0][1]]:heapq.heappop(max)
while min and not visited[min[0][1]]:heapq.heappop(min)
if max and min:
print(-max[0][0], min[0][0],sep=' ')
else:
print('EMPTY')
|
cs |