[Python] 프로그래머스 LV.03 - 이중우선순위큐

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

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

[ 알고리즘 ]

힙 큐 알고리즘

 

[ 접근 방법 ]

최대힙과 최소힙 두개를 써서 해결하느냐, 최소힙 하나로 해결하느냐로 결정되는 문제이다.

 

최소힙에서 최대값을 pop할 수 없으니 다른 방법으로 생각을 해봐야한다.

그렇다고 Level.03 문제인데 힙을 2개를 써서 무식하게 풀라고 낸 문제는 아닌 것 같았다.

 

해답은 heapq.nsmallest에 있다.

heapq.nsmallest(n,iterable) 을 사용하여 가장 최대인 값을 제외하고 최소인 것들로 다시 힙을 만들어주면된다.

 

백트래킹 풀다가 이 문제를 보니 너무 사랑스러울 지경이다 ㅎ ㅎ..

 

[ 코드 ]

import heapq

def solution(operations):
    heap = []

    for data in operations:
        a = data.split(' ')[0]
        b = data.split(' ')[1]

        if a == 'I':
            b = int(b)
            heapq.heappush(heap, b)

        elif a == 'D':
            if len(heap) == 0:
                continue
            if b == '-1':
                heapq.heappop(heap)
            else:
                heap = heapq.nsmallest(len(heap) - 1, heap)
    

    if len(heap)==0:
        return [0,0]
    else:
        return[max(heap),min(heap)]