[힙] 프로그래머스 이중우선순위큐 파이썬 풀이

이중우선순위큐 파이썬 풀이

---

접근 방법

문제 상에서 operation의 최대값과 최소값을 Delete하는 연산엔 pop과 heappop을 섞어 풀면 되지않을까 싶어서 요구사항대로, 케이스별로 풀었다.

1차 작성 코드

import heapq as hq

def solution(op):
        q = []
        for i in op:
            ins, num = i.strip().split() 
            if ins == 'I':
                hq.heappush(q, int(num))
            elif ins == 'D' and q:
                if num == '-1':
                    hq.heappop(q)
                elif num == '1':
                    q.pop()
        return [max(q), min(q)] if q else [0,0]

operation이 op라는 배열로 주어졌을 때, 각 명령어의 문자인 instruction과 숫자부 number를 나누어 ins, num 변수에 할당했다.
그리고 각각의 문자를 조건에 넣고 명령대로 수행했다.

1차 코드 문제점

이 문제의 다른 풀이들을 보면, 노드를 직접 구현한 걸 볼 수 있다. 내가 작성한 1차 코드처럼 풀면 heap 트리 구조가 유지되지 않는다고 한다. 직관적인 테케 예를 살펴보자. ["I 6", "I 2", "I 1", "I 4", "I 5", "I 3", "D 1", "I 7", "D -1", "I 6", "D -1", "D -1"] 라는 테스트 케이스에 대해서 프로그램은 [7,4]를 리턴해야한다. 하지만, 내 프로그램은 [7,5] 를 리턴한다.

힙 자료구조에서 그렇듯 파이썬 heapq 모듈은 root노드에 대해서 minheap이거나 maxheap을 보장할 수 있다. 그러나, 하위 노드들의 우선순위는 보장할 수 없다. 그러므로, maxheap과 minheap 두 개를 구현하고 Instruction을 수행한 후에 각각 힙 구조에 담겨있는 원소를 비교 및 매칭하여 출력하는 이중 구조를 구현해야 한다.