[프로그래머스 level3 이중우선순위큐] heapq 활용하기

해결해야하는 문제는 다음과 같았다.

https://programmers.co.kr/learn/courses/30/lessons/42628

코딩테스트 연습 - 이중우선순위큐

 

파이썬에서는 heapq를 활용하여 heap으로 배열을 만들어 간단하게 구할 수 있도록 하기 때문에 이를 활용하고자 하였다.

(나중에 직접 tree 클래스를 생성하여 만들어본다던가,, 그런 과정도 해봐야 될 것 같다..ㅎㅎ)

 

우선 I인 경우 들어오는 수를 저장하기 위한 heap을 생성하였다. 이는 heap자료구조 형태로 저장될 수 있도록 하였다.

I가 들어와서 값을 삽입해야하는 경우 heapq의 heappush를 활용하였고,

D가 들어온 경우, 1이면 최댓값을 제거해야하므로, 최댓값은 heap의 가장 마지막 원소일 것이기 때문에 pop으로 빼주었다.

그리고 -1이면 최솟값을 제거해야하므로 ,최솟값은 heapq에서 heappop을 활용하면, 최소힙에서 가장 작은 값을 빼주므로 heapq를 활용하였다.

 

그리고 마지막에 answer에는 heap이 비어있다면 0이 최댓값, 최솟값으로써 담길 것이고, 비어있지않다면 heap의 최댓값 최솟값을 담을 수 있도록 하였다.

 

이러한 아이디어를 바탕으로 작성한 코드는 다음과 같다.

import heapq

def solution(operations):
    heap = []
    heapq.heapify(heap)
    for op in operations :
        op_split = op.split()
        if op_split[0]=='I' :
            heapq.heappush(heap,int(op_split[1]))
        else :
            if op_split[1]=='1' and heap:
                heap.pop()
            elif op_split[1]=='-1' and heap:
                heapq.heappop(heap)
    answer = [max(heap) if heap else 0, min(heap) if heap else 0]
    return answer