[프로그래머스] lv3. 이중우선순위큐 풀이 (Python)

프로그래머스

lv3. 이중우선순위큐

접근한 방법

문제에서 우선순위큐를 쓰고 있으므로 우선순위 큐를 사용할 수 있는 heapq 라이브러리를 사용합니다.

두 개의 힙큐(최대힙, 최소힙)를 사용해서 최댓값과 최솟값을 관리하면 됩니다.

 

Insert일 경우에는 두 힙에 모두 값을 넣어주고 최대힙의 경우 음수로 관리하면 구현할 수 있습니다.

Delete일 경우 두 힙에서 동일한 값을 모두 빼주어야 하는데 최댓값을 빼는 경우 최소힙에서는 최대힙에서 pop된 값에 음수를 붙여 제거해야 값을 찾을 수 있으며 최솟값을 빼는 경우 최대힙에서도 마찬가지로 최소힙에서 pop된 값에 음수를 붙여 제거해야 값을 찾을 수 있습니다.

 

힙에 값이 남아있지 않다면 0, 0을, 남아있다면 최대힙과 최소힙을 출력하면 됩니다.

def solution(operations):
    import heapq
    maxh, minh = [], []
    for oper in operations:
        op, now = oper.split()
        if op == "I":
            heapq.heappush(maxh, -int(now))
            heapq.heappush(minh, int(now))
        elif op == "D":
            if not maxh:
                pass
            elif now == "1":
                minh.remove(-heapq.heappop(maxh))
            elif now == "-1":
                maxh.remove(-heapq.heappop(minh))
    return [- heapq.heappop(maxh), heapq.heappop(minh)] if maxh else [0, 0]

 

효율성 테스트가 왜 없는지..?