Lv.3_이중우선순위큐

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

프로그래머스

import heapq

def solution(operations):
    answer = []
    
    for operation in operations:
        word, number = operation.split()
        number = int(number)
        
        if word == 'I':
            heapq.heappush(answer, number)
            
        elif word == 'D' and number == 1:
            if len(answer) != 0:
                max_value = max(answer)
                answer.remove(max_value)
        
        else:
            if len(answer) != 0:
                heapq.heappop(answer)
    
    if answer:
        return [max(answer), min(answer)]
    return [0, 0]

 

이 문제는 heapq를 사용하면 효율성 있게 풀 수 있는 문제다.

 

힙은 0부터 요소를 셀 때, 모든 k에 대해 a[k] <= a[2*k+1]와 a[k] <= a[2*k+2]가 유지되는 배열이다.

A가 B의 부모노드이면 A의 키 값과 B의 키 값 사이에는 대소관계가 자동으로 성립되게 된다

 

출처 https://stackabuse.com/guide-to-heaps-in-python/

 

import heapq를 이용하여 사용할 수 있다

 

● heapq.heappush(heap, item): item을 heap에 추가

● heapq.heappop(heap) : heap에서 가장 작은 원소를 pop

 

heapq을 기억해두자