[프로그래머스] LV.3 이중우선순위큐 (Python) - heapq

 

 

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

프로그래머스

 

 

 

 

처음 제출한 코드

import heapq
def solution(operations):
    heap = []
    for operation in operations:
        if operation.startswith("I"):
            num = int(operation.split()[1])
            heapq.heappush(heap, num)
        elif operation == 'D 1':
            if not heap:
                continue
            max_heap = []
            min_heap = []
            for element in heap:
                heapq.heappush(max_heap, -element)
            heapq.heappop(max_heap)
            for element in max_heap:
                heapq.heappush(min_heap, -element)
            heap = min_heap
        else:
            if not heap:
                continue
            heapq.heappop(heap)
    if not heap:
        return [0, 0]
    else:
        return [max(heap), min(heap)]

 

 

max heap을 따로 만들어서 기존 최소 힙의 모든 원소를 -를 붙여 옮긴 뒤 heappop하는 방식이다. 더 좋은 방식이 있을까 싶어 찾아봤는데, 파이썬에서는 heapq모듈로 리스트를 힙처럼 사용하는 것이기 때문에 힙처럼 쓰고 있는 것도 사실은 '리스트'라는 사실을 알았다. 따라서 리스트 연산이 모두 사용 가능하다. 

 

 

개선된 코드

def solution(operations):
    heap = []
    for operation in operations:
        if operation.startswith("I"):
            num = int(operation.split()[1])
            heapq.heappush(heap, num)
        elif operation == 'D 1':
            if not heap:
                continue
            maxx:int = max(heap)
            heap.remove(maxx)
        else:
            if not heap:
                continue
            heapq.heappop(heap)
    if not heap:
        return [0, 0]
    else:
        return [max(heap), min(heap)]