[프로그래머스/Lv. 3] - 이중우선순위큐

이중우선순위큐 문제 링크

아이디어

처음에 min heap, max heap을 따로 만들어서 최댓값과 최솟값을 처리해주고자 했다.
연산을 편하게 하기 위해서 따로 만들었는데, 내부적으로 삭제 연산 시, max heap에서도 최솟값을 삭제해야하고 min heap에서도 최댓값을 삭제해야 하는 배보다 배꼽이 더 커졌다.

그래서 min heap을 하나만 만들되, 최댓값을 어떻게 찾을 수 있을지 생각해봤다.
찾아보니, heap은 근본이 리스트이기 때문에 리스트에서 사용할 수 있는 함수를 모두 사용할 수 있다.

코드

import heapq
def solution(operations):
    q = []
    for operation in operations:
        op, num = operation.split() # 명령어, 데이터
        num = int(num)
        if op == "I": # 삽입
            heapq.heappush(q, num)
        elif op == "D": # 삭제
            # 큐가 비어있다면 연산 무시하기 위한 처리
            if q:
                if num == 1: # 최댓값 삭제
                    _max = max(q)
                    q.remove(_max)
                else: # 최솟값 삭제
                    heapq.heappop(q)
            
    return [0, 0] if not q else [max(q), heapq.heappop(q)]

풀이

min heap을 선언한다.
삽입 연산은 단순히 삽입하면 되고 삭제 연산은 먼저 큐가 비어있지 않은 경우를 처리해준다.
그리고, 최댓값을 삭제해야 한다면, max()로 최댓값을 찾고 remove() 해준다.
최솟값은 min heap이므로 heappop()을 사용한다.