백준(BOJ) 7662 이중 우선순위 큐(Python)

문제 내용

 

solved.ac의 Class 3에 있던 문제.

예전에 한 번 풀어보려 했다가 알고리즘 구상이 귀찮아서 미뤘는데, 이번에 하게 됐다.

​

최소 힙과 최대 힙을 동시에 사용해서 풀었다.

최소 힙과 최대 힙은 그 값의 부호 차이로 결정되는데, 값을 힙에 집어넣을 때 고유 넘버를 설정해주고, 값을 뺄 때 그 넘버에 해당하는 매핑 리스트 내의 값을 수정해준다. 최소 힙과 최대 힙에서 같은 값을 동시에 뺄 수 없기 때문에, 나중에 값이 등장하더라도 그 값이 이미 처리됐음을 기록할 수 있게 된다. 그 후에는 최소 힙과 최대 힙에 고유 넘버에 해당하는 매핑 리스트 값이 1인 값이 남아있다면 최솟값과 최댓값을 출력하게 되고, 없었다면 EMPTY를 출력한다.

​

코드는 다음과 같다.

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
#input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

t=int(input())
for i in range(t):
    n=int(input())
    Map=[1]*n
    L1=[]
    L2=[]
    for j in range(n):
        a,b=input().split()
        b=int(b)
        if a=='I':
            heapq.heappush(L1,(b,j))
            heapq.heappush(L2,(-b,j))
        else:
            if b==1 and L2:
                while L2:
                    x,y=heapq.heappop(L2)
                    if Map[y]:
                        break
                Map[y]=0
            elif b==-1 and L1:
                while L1:
                    x,y=heapq.heappop(L1)
                    if Map[y]:
                        break
                Map[y]=0
    flag=0
    while L2:
        a,b=heapq.heappop(L2)
        if Map[b]:
            flag=1
            print(-a,end=' ')
            break
    while L1:
        a,b=heapq.heappop(L1)
        if Map[b]:
            flag=1
            print(a)
            break
    if not flag:
        print('EMPTY')

)

처음에는 힙 하나로 어떻게 풀 수 있는 방법이 없나 이것저것 생각해봤지만, 결국 최소 힙과 최대 힙을 사용해서 문제를 해결했다.

고유 넘버를 지정해주는 작업은 나름 익숙해져있어서 떠올리는게 크게 어렵지 않았다. 오히려 바로 떠올랐을 정도.