[Programmers] 이중우선순위큐

[Programmers] 이중우선순위큐

 

🎈문제

https://programmers.co.kr/learn/courses/30/lessons/42628

💬설명

• python heapq를 이용해서 풀었다.
• 최대힙, 최소힙 모두 써줘야 했기 때문에 두 힙의 동기화가 중요했다.
• 최대값 pop할 때 최소힙에서도 삭제해주고, 최소값 pop 할때 최대힙에서도 삭제해주면 된다.

+ 다른 사람 코드도 찾아보니 굳이 두개의 heap을 사용하지 않고 최소힙에서 heapq.nlargest(n, hq) 이렇게 해주면 큰값 순서대로 n개 뽑힌다고 한다. 그럼 heapq.nlargest(1, hq)이렇게 해주면 된다.

👩‍💻코드

import heapq


max_hq = []
min_hq = []


def solution(operations):
    answer = []
    
    for operation in operations:
        op, num = operation.split(" ")
        
        if op == "I":
            heapq.heappush(max_hq, (-1 * int(num), int(num)))
            heapq.heappush(min_hq, int(num))
        elif op == "D":
            if not max_hq:
                continue
            if num == "1":
                value = heapq.heappop(max_hq)[1]
                min_hq.remove(value)
            elif num == "-1":
                value = heapq.heappop(min_hq)
                for i in range(len(max_hq)):
                    if max_hq[i][1] == value:
                        del max_hq[i]
                        break
                        
    if max_hq:
        return [heapq.heappop(max_hq)[1], heapq.heappop(min_hq)]
    else:
        return [0, 0]
    return answer