[프로그래머스] 이중우선순위큐 (파이썬)

📕 문제

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

코딩테스트 연습 - 이중우선순위큐

 

💡 풀이법

: 최대힙과 최소힙을 두개 만들어서 삽입할 때는 두개 다 넣고, 최대값을 삭제할 때는 최대힙에서 빼고, 최소값을 삭제할 때는 최소힙에서 뺀다. (단, 뺄 때 다른 힙에서는 뺀 원소를 삭제해줘야함)

import heapq

def solution(operations):
    answer = [0,0]
    min_heap = []
    max_heap = []
    cnt = 0

    for o in operations:
        oper = o.split()
        if oper[0] == 'I':
            num = int(oper[-1])
            heapq.heappush(min_heap, num)
            heapq.heappush(max_heap, -num)
            cnt += 1
        else:
            if cnt:
                if '-' in o:
                    num = heapq.heappop(min_heap)
                    max_heap.remove(-num)
                else:
                    num = heapq.heappop(max_heap)
                    min_heap.remove(-num)
                cnt -= 1

    if cnt:
        M = heapq.heappop(max_heap)
        m = heapq.heappop(min_heap)
        answer = [-M, m]

    return answer