[백준/Python] 7662 우선순위 큐

문제링크

7662번: 이중 우선순위 큐

 

문제풀이

참고한 블로그

https://imzzan.tistory.com/31

[백준][Python] 7662번 이중 우선순위 큐

 

우선순위 큐는 heap으로 구현이 가능합니다.

파이썬에서 내장 모듈인 heapq로 heap을 구현할 수 있는데 이는 minheap 이 디폴트입니다.

따라서 maxheap을 구현하기 위해서는 value에 -1 을 곱하는 방식으로 구현을 해야합니다.

이중 우선순위 큐는 maxheap , minheap 을 두개를 서로 visit배열을 사용해서 연결한 것입니다.

 

왜 튜플을 사용하여 (value, index) 값을 넣어주었냐면 

최소힙에서 pop을 시켰을때 최대힙은 그 값이 어디있는지 알 수 없습니다. 따라서 제 코드에서는 done 이라는 visit 함수를 만들어서

최대힙에서 pop을 해야할 경우 트리구조 상위에 있는 값을 done 배열을 참조하여 True 일 경우에는 이미 제거된 값으로 간주하여 while 문을 사용하여 pop을 해주게 되는 것입니다. 그후 while 문을 돌며 이미 최소힙에서 제거된 값이 모두 최대힙에서도 최신화가 되면 

이제 else 문을 통해 최대힙에서 pop을 해주게 됩니다.

반대의 경우도 마찬가지입니다.

 

그 후 마지막으로 한번더 while문을 돌려주어서 두개의 힙을 동일하게 맞추어줍니다. 이를 다른 블로그에서는 쓰레기값을 제거한다는 표현을 썼습니다.

 

import heapq
import sys
testDataNumber = int(input())
# 우선순위 큐 = heap
# 이중 우선순위 큐 = maxheapq , minheapq 를 visit 배열을 사용해서 서로 연결한 것.
# heapq 의 디폴트는 최소힙 따라서 최대힙을 구현하기 위해서는 value에 -1 값을 넣어주므로써 구현이 가능
strr = ''
for i in range(testDataNumber) :
    maxhq = []
    minhq = []
    expressionNumber = int(input())
    done = [False]* expressionNumber
    for j in range(expressionNumber):
        # print(j)
        a,b = sys.stdin.readline().strip().split(" ")
        # print(a,b)
        if a == 'I' :
            heapq.heappush(maxhq,((-1)*int(b),j))
            heapq.heappush(minhq, (int(b),j))          
        if a == "D" :
            if b == '-1':
                while minhq :
                    if done[minhq[0][1]] :
                        heapq.heappop(minhq)
                    else :
                        if minhq :
                            minn = heapq.heappop(minhq)
                            done[minn[1]] = True
                        break
            elif b == '1':
                while maxhq :
                    if done[maxhq[0][1]] :
                        heapq.heappop(maxhq)
                    else :
                        if maxhq :
                            maxx = heapq.heappop(maxhq)
                            done[maxx[1]] = True
                        break
    while minhq :
        if done[minhq[0][1]] :
            heapq.heappop(minhq)
        else :
            break
    while maxhq :
        if done[maxhq[0][1]] :
            heapq.heappop(maxhq)
        else :
            break
    if minhq :
        strr += f'{-1* maxhq[0][0]} {minhq[0][0]}\n'
    else :
        strr += 'EMPTY\n'

print(strr)