[Programmers] 이중우선순위큐 (Python)

문제

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

프로그래머스

 

풀이과정

파이썬의 heapq 같은 경우 최소힙이므로 최대, 최소값을 번갈아 가며 구해야 하기 때문에 별도의 저장공간을 활용했다. 연산이 종료된 후 최대, 최소값을 가진 리스트의 교집합을 구하기에는 메모리 낭비가 있다고 판단되어 최대값을 구하는 경우에만 최대값 리스트값을 힙에서 빼 준 후 재정렬을 수행했다. 

1. "I" 인 경우 heap에 삽입 

2. "D"인경우
    2-1. 최대값 삭제 : 가장 큰 수를 구해서 heap에서 제거. 이때 set 자료구조를 사용했으므로 힙정렬 수행
    2-2. 최소값 삭제 : 최소값 삭제

3. heap에 숫자가 없는 경우 패스하고 다음 연산 수행

 

Script

import heapq

def solution(operations):
    heap = []
    heap_max = []

    for oper in operations:
        act, num = oper.split(" ")
        if act == "I":
            heapq.heappush(heap, int(num))
        else:
            num = int(num)
            if heap:
                if num == 1:
                    heap_max += heapq.nlargest(1, heap)
                    heap = list(set(heap) - set(heap_max))
                    heapq.heapify(heap)
                else:
                    heapq.heappop(heap)
            else:
                pass
    if heap:
        answer = [max(heap), min(heap)]
    else:
        answer = [0, 0]
    return answer