프로그래머스 고득점 Kit - 이중 우선순위 큐

Problem

https://school.programmers.co.kr/learn/courses/30/parts/12117

프로그래머스

 

• 이중 우선순위 큐는 다음 연산을 할 수 있다

명령어	연산 내용
I 숫자	큐에 주어진 숫자를 삽입
D 1	큐에서 최댓값을 삭제
D -1	큐에서 최솟값을 삭제

• 이 중 우선순위 큐가 할 연산이 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0, 0] 을 반환해라
• 비어있지 않으면 [최댓값, 최솟값]을 반환해라.

Input / Output Examples

operations	return
["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"]	[0,0]
["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"]	[333,-45]

Solution

우선순위 큐를 하나만 사용하여 해당 문제를 풀 수 있다.

하지만 아래 코드가 효율적인 코드라고는 확답을 하기 어렵다.

 

숫자 삽입은 큐에 해당 숫자를 넣어주면 된다.

파이썬의 우선순위 큐는 minHeap을 기반으로 구현되어 있기에, 최솟값 삭제는 큐에서 pop을 해주면 된다.

최댓값의 경우, 해당 큐에서 최댓값을 찾은 후 remove로 지워버린다.

이후에 heapify를 사용해 다시 minHeap 구조가 유지되도록 한다.

Code

import heapq

def solution(operations):
    answer = [0,0]
    heap = []
    for i in operations:
        oper = i[0]
        value = int(i.split(" ")[1])
        
        if oper == "I":
            heapq.heappush(heap,value)
        elif len(heap) == 0: # 큐가 빈 경우, 무시
            continue
        elif oper == "D" and value == -1:
             heapq.heappop(heap)
        else:
            heap.remove(max(heap))
            heapq.heapify(heap)

    if len(heap) == 0: # 빈 경우 
        return [0,0]
    if len(heap) == 1: # 값이 하나만 있는 경우
        i = heapq.heappop(heap)
        return [i,i]
    
    answer[1] = heapq.heappop(heap) #최솟값
    heap.sort(reverse=True)
    answer[0] = heap[0] #최댓값
    return answer