프로그래머스 Lv3 이중우선순위큐 Python

문제 링크

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

프로그래머스

정답 코드

import heapq
def solution(operations):
    maxHeap = []
    minHeap = []
    for operation in operations:
        oper, number = operation.split()
        number = int(number)
        if oper == "I":
            heapq.heappush(maxHeap, -number)
            heapq.heappush(minHeap, number)
        else:
            if number == 1:
                if maxHeap:
                    maxNumber = heapq.heappop(maxHeap)
                    minHeap.remove(-maxNumber)
            else:
                if minHeap:
                    minNumber = heapq.heappop(minHeap)
                    maxHeap.remove(-minNumber)

    answer = []
    if maxHeap:
        answer = [-maxHeap[0], minHeap[0]]
    else:
        answer = [0, 0]
    return answer

풀이 방법

# 힙 불러오기
import heapq
# 힙 만들기
# 최대 힙
maxHeap = []
# 최소 힙
minHeap = []
# 힙 저장하기
number = 777
heapq.heappush(maxHeap, -number)
heapq.heappush(minHeap, number)
# 힙 원소 리턴 (가장 작은 원소를 리턴함)
minNumber = heapq.heappop(minHeap)
maxNumber = -heapq.heappop(maxHeap)

# --- 추가 heapq 함수 ---
# 기존 자료형을 힙 자료형으로 변환
list = [3, 1, 2]
heap = heapify(list)
# 출력하면
# heap = [1, 3, 2]

느낀점

- remove 사용하면 시간초과 날 줄 알았는데 꼭 그러지는 않는다.

- 기본적인 heap의 구조: 최소 값을 뿌리 노드에 저장한다.