백준 7662 이중 우선순위 큐

OWLS·2023년 11월 2일

문제

분석

원래 사용되는 우선순위 큐를 모른다면 그걸 먼저 풀고 오는걸 추천함.

우선순위 큐는 특정 기준으로 데이터들을 정렬하며 삽입하고 빼낼때 고르고 log(n) 시간복잡도를 가져서 데이터의 크기가 크면 클수록 안정적으로 빠르게 데이터를 뽑아 낼 수 있는 장점이 있음.

기존 우선순위큐는 특정 기준으로 내림차순이든, 오름차순이든, 정렬을 해버리기 때문에 데이터를 빼낼 때는 머리 부분만 가능함.

그러나 이 문제에서는 하나의 자료 구조에서 min heap과 max heap을 동시에 수행할 수 있는 걸 원했지만, 이런게 있었으면 min heap, max heap으로 굳이 나누기 전에 다양한 구조체로 구현이 되었을 것임.

따라서 해당 기능을 수행하는 구조체가 아닌 로직을 구현해야한다는 결론에 도달함.

아이디어 그래도 기존 우선순위 큐를 사용하자

이러나 저러나 기존에 쓰인 우선 순위 큐는 좋음.
특히 본인이 수행하는 파이썬 환경에선 heapq라는 강력한 라이브러리를 제공해줌. 이를 사용하지 않을 이유가 없다고 느낌.

따라서 heapq로 min heap과 max heap을 만듦. 하나는 가장 큰수가 먼저 나오도록, 다른 하나는 가장 작은 수가 먼저 나오도록 설정함.

그리고 값을 입력받으면 각각의 힙에 삽입함.

따라서 우선순위가 높은걸 삭제하라고 하면 max heap에서 빼고, 낮은걸 삭제하라고 하면 min heap에서 뺌.

이러면 두개가 관리가 안됨. 그래서 이를 num의 tag로 관리함. 입력 받는 순서에 맞춰서 tag를 넣어 데이터의 종류를 식별함. 이를 remove, add, in 연산자가 O(1)인 set에 넣어서 관리함. tag에서 num으로 이어지는 보조 dict() 구조체를 넣어서 관리함.

이를 통해서 set에 있는 tag의 숫자라면 아직 제거 되지 않았다는 뜻이니 그대로 뽑고, set에 없는 tag의 숫자라면 이미 다른 쪽 연산에서 제거되었다는 뜻이니 무시하고 다음 pop을 진행하는 방식으로 감.

구현

import sys
from heapq import heappush, heappop

# 빠른 입출력을 위해 sys.stdin.readline을 사용
input = sys.stdin.readline

t = int(input())


for _ in range(t):
    
    # maxheap
    hq = []
    
    # minheap
    lq = []
    
    # tag set
    whole = set()
    
    # tag2Num
    tag2Num = dict()
    
    k = int(input())
    numTag= 0
    for _ in range(k):
    	# Command form is that "X" n
        # X is kind of Alphabet, 0 is kind of Number
        command = input().strip().split()
        
        # convert num that is str type to int type
        command[1] = int(command[1])
        
        
        # I is insert. 
        if command[0] == "I" :
        
        	# insert Num to maxheap and minheap
            heappush(hq,(-command[1],numTag))
            heappush(lq,(command[1],numTag))
            
            # And also add num to tag set
            whole.add(numTag)
            tag2Num[numTag] = command[1]
            
            # update numTag
            numTag += 1
            pass
        else: # command is D. It means that function is pop
        
        	# if command[1] is 1, it is max heap remove function
            if command[1] == 1:
                while hq:
                    value, curNumTag = heappop(hq)
                    
                  	# If curNumTag is not removed, execute to pop, else discard this and continue to pop again.
                    if curNumTag in whole:
                        whole.remove(curNumTag)
                        break
                    else: pass
        		# if command[1] is -1, it is min heap remove function        
            else:
                while lq:
                    value, curNumTag = heappop(lq)
                    
                    # similar to hq part.
                    if curNumTag in whole:
                        whole.remove(curNumTag)
                        break
                    else: pass
                
            
    # whole is set of numtag in heap structure. 
    # if len (whole) is larger than 0, find max, min value
    if len(whole) > 0 :
        maxValue  = None
        minValue = None 
        
        # find all num tag in whole 
        # and find max and min value
        for tag in whole:
            num = tag2Num[tag]
            if maxValue == None:
                maxValue = num
                minValue = num
            else:
                maxValue = max(maxValue,num)
                minValue = min(minValue, num)
        print(maxValue, minValue)
    # if whole is Empty, then print "EMPTY
    else:
        print("EMPTY")