[알고리즘] 프로그래머스 | 이중우선순위큐

이중우선순위큐

답: 

힙 하나로 구현하기

from heapq import heappush, heappop

def solution(operations):
    heap = []
    for operate in operations:
        o = operate.split(" ")
        alpha, num = o[0], int(o[1])    
        if alpha == "I":
            heappush(heap, num)
        elif alpha == "D":
            if heap and num == -1:
                heappop(heap)
            elif heap and num == 1:
                heap.pop()
    if len(heap) > 0:
        return [max(heap), heap[0]] 
    return [0,0]

 

min_heap, max_heap으로 구현하기

from heapq import heappush, heappop

def solution(operations):
    min_heap = []
    max_heap = []
    # 푸는 중...

 

 

문제 분석 및 해석

list형태의 operations이 주어지고, 아래 문자열들이 포함되어있다.

 

명령어수신 탑(높이)

I 숫자   큐에 숫자 삽입

D 1   큐에서 최댓값 삭제

D -1  큐에서 최솟값 삭제

 

이중 우선순위 큐를 구현해보는 문제

 

 

 

>> 풀이생각

 

operations를 반복문으로 돌리며 split으로 나누어 받고

그때그때 alphabet을 확인하고

heap에 heappush heappop하면서 최솟값과 최댓값을 추가 및 삭제하자.

 

len(heap) > 0 이면 [최댓값, 최솟값의 결과]

heap이 비었으면 [0, 0]

 

 

 

 

 

리뷰.

 

 

*** heap을 쓸 때 늘 유의할 사항

아래와 같이 코드를 작성하면  테스트케이스 6번이 실패한다.

가장 첫번째 요소는 min값을 보장하지만 max값은 위치를 알 수 없다

 

if len(heap) > 0:
    return [heap[-1], heap[0]] 
    # 힙은 첫번째 요소가 min값이지만 max값이 -1에 있다고 보장할 수 없음
return [0,0]