7662 이중 우선순위 큐

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

7662번: 이중 우선순위 큐

 

내 풀이(구글링해서 찾아보고 안보고 풀음)

import heapq

t = int(input())
rst = []
for i in range(t):
    n = int(input())
    chk = [False]*1_000_001
    max = []
    min = []
    for j in range(n):
        x = list(input().split())
        if x[0] == 'I':
            heapq.heappush(max, (-int(x[1]), j))
            heapq.heappush(min, (int(x[1]), j))
            chk[j] = True
        else:
            if x[1] == '1':
                while max and not chk[max[0][1]]: heapq.heappop(max)
                if max:
                    chk[max[0][1]] = False
                    heapq.heappop(max)
            else:
                while min and not chk[min[0][1]]: heapq.heappop(min)
                if min:
                    chk[min[0][1]] = False
                    heapq.heappop(min)
    
    while max and not chk[max[0][1]]: heapq.heappop(max)
    while min and not chk[min[0][1]]: heapq.heappop(min)

    rst.append([])
    if max and min:
        m = max[0][0]
        rst[i].append(-max[0][0])
        rst[i].append(min[0][0])
    else:
        rst[i].append("EMPTY")
for i in rst:
    if len(i) == 1:
        print(i[0])
    else:
        print('{} {}'.format(i[0], i[1]))

max는 최대힙, min은 최소힙이다. chk는 각 번호마다 id를 부여해 false면 삭제한다. 최대힙은 -를 붙여서 넣어서 구현했다.

                while max and not chk[max[0][1]]: heapq.heappop(max)

이런 부분에서는 힙이 있고 chk의 id가 false면 삭제하라는 의미이다. 그리고 마지막에 또 해줘서 false인 것을 완전히 삭제한다. 

그리고 format 함수를 사용하여 결과값을 출력했다.