https://www.acmicpc.net/problem/7662
7662번: 이중 우선순위 큐입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적www.acmicpc.net
그냥 정렬해서 풀면 간단한데, 시간 때문에 개고생을 해야된다.
힙과 defaultdict 를 이용한다.
minheap과 maxheap을 만들어서, 원소를 각각 추가해 준다 이때 defaultdict로 수가 몇개 들어있는지 확인한다.
그리고 최소값은 minheap에서, 최댓값은 maxheap에서 뺀다.
이때, 만일 다른 힙에서 삭제된 값일수도 있으니, defaultdict에 현재 pop한 값이 1개 이상일 때까지 (유효한 수가 존재)
pop해준다.
만일 유효한 수를 찾았다면, defaultdict[유효한수] 에서 1을 빼준다.
import heapqimport sysfrom heapq import *from collections import defaultdict
input = sys.stdin.readlinet = int(input())for _ in range(t): k = int(input())
minh, maxh, dd = [], [], defaultdict(int) for _ in range(k):
a, b = input().rstrip().split() b = int(b) if a == "I":
heappush(minh, b) heappush(maxh, -b)
dd[b] += 1 else: if b == 1: # 최댓값을 삭제하는 연산이라면
while True: try:
tmp = -heappop(maxh)
if dd[tmp] > 0: dd[tmp] -= 1
break except:
break elif b == -1: # 최소값을 선택하면
while True: # 삭제된 값이 아닐때까지 try:
tmp = heappop(minh)
if dd[tmp] > 0: dd[tmp] -= 1
break except:
break try: while True:
minval = heappop(minh) if dd[minval]:
break except: print("EMPTY") continue
while True: maxval = -heappop(maxh) if dd[maxval]:
break print(maxval, minval)