[python]7662번 이중 우선순위 큐

어려웠다. 단순히 따로따로 최대힙,최소힙 배열을 만들고

돌리기에는 서로 반영이 안돼 오답이 출력되었다.

 

그렇다면 서로 다른 배열을 어떻게 하면 연동 시킬 수 있을지 고민하다 찾아본 결과 

새로운 배열을 만들어 각각 호출한 값의 고유 key값을 부여하여 삭제되었는지 여부를 확인하는 것이었다.

 

from heapq import heappush,heappop
import sys
input = sys.stdin.readline
for _ in range(int(input().strip())):
    call = int(input().strip())
    stgmax = []
    stgmin = []
    visit = [False for i in range(1000001)] #문제에서 총 100000번의 호출이 있기에 100000가지의 고유한 숫자들을 만들 수 있다.
    for i in range(call):
        calli,calln = input().split()
        if calli == 'I':
            heappush(stgmax,(int(calln)*-1,i)) #최대힙 구현
            heappush(stgmin,(int(calln),i)) #최소힙
            visit[i] = False #이번 호출된 값의 순번으로 고유값 지정
        else:
            if calln == '-1':
                while stgmin and visit[stgmin[0][1]]: #최대힙에서 삭제된 값이 남아있을 수도 있기에
                    heappop(stgmin)
                if stgmin:
                    visit[heappop(stgmin)[1]] = True #삭제와 동시에 고유값에 해당하는 visit값 갱신
            else:
                while stgmax and visit[stgmax[0][1]]: #최소힙에서 삭제된 값이 남아있을 수도 있기에
                    heappop(stgmax)
                if stgmax: #삭제와 동시에 고유값에 해당하는 visit값 갱신
                    visit[heappop(stgmax)[1]] = True
    while stgmin and visit[stgmin[0][1]]: #남아있는 visit True 값들 삭제
        heappop(stgmin)
    while stgmax and visit[stgmax[0][1]]:
        heappop(stgmax)
    if stgmin and stgmax:
        print(stgmax[0][0]*-1,stgmin[0][0])
    else:
        print('EMPTY')