[힙] 프로그래머스 Lv3. 이중우선순위큐 - Python

🗂️ 문제

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

프로그래머스

 

💡 접근법

처음에는 min heap과 max heap을 각각 생성하고 이를 통해 최댓값, 최솟값을 찾아주려고 했다. 하지만 이렇게 하면 일일히 min heap에서 삭제된 값을 max heap에서도 찾아 삭제해야 한다는 단점이 있다. 따라서 하나의 힙을 생성하여 문제를 해결한다.

 

최소 힙에서 최댓값을 구하는 방법은 다음과 같다.

1. 힙 자료구조 또한 리스트 기반이기 때문에 max(heap) 함수를 통해 최댓값을 구할 수 있다.
2. 힙에서 최댓값 N개를 뽑아주는 heapq.nlargest(1, heap)[0]을 통해 최댓값을 구할 수 있다.

 

😎 내 코드

import heapq

def solution(operations):
    heap = []
    
    for oper in operations:
        ch, num = oper.split(' ')
        num = int(num)
        
        if ch == "I":  # 삽입 연산
            heapq.heappush(heap, num)

        elif ch == "D" and len(heap):  # 삭제 연산
            if num == -1:  # 최솟값 삭제
                heapq.heappop(heap)
            elif num == 1:  # 최댓값 삭제
                heap.remove(max(heap))
    
    if heap:
        return [max(heap), heapq.heappop(heap)]
    else:
        return [0,0]

 

🧐 배운 점

• 최소 힙에서 최댓값을 구하는 방법
  1. 힙 자료구조도 리스트 기반이기 때문에 max()를 통해 최댓값을 구할 수 있다.
  2. 최댓값 N개를 뽑아주는 heapq.nlargest(1, list)를 통해 최댓값을 구할 수 있다.