Programmers / 3단계 / 이중우선순위큐 / python / heapq

 

코딩테스트 연습 - 이중우선순위큐 | 프로그래머스 스쿨 (programmers.co.kr)

 

 

모범 답안

import heapq
def solution(operations):
    q = []
    for i in operations:
        oper, num = i.split()
        num = int(num)
        if oper == 'I':
            heapq.heappush(q, num)
        elif oper == 'D' and num == 1:
            if len(q) != 0:
                q.remove(max(q))
        else:
            if len(q)!=0:
                heapq.heappop(q)
            
    if len(q) == 0:
        answer = [0,0]
    else:
        answer = [max(q), heapq.heappop(q)]
    return answer

 

학습한 것

heap에 대한 개념 정리가 부족하였다.

heapq.heappop()을 사용해 힙에서 원소를 꺼낼 때에는 항상 가장 작은 값이 나온다.

파이썬의 힙은 최소 힙(Min Heap)으로 구성되어 있으므로 단순히 원소를 힙에 전부 넣었다가 빼는 것만으로도 시간 복잡도 O(NlogN)에 오름차순 정렬이 완료된다.

 

 

+) 최대 힙을 heapq로 구현하여 내림차순 힙 정렬을 구현하는 경우

import heapq

def heapsortDesc(iterable):
    h = []
    result = []
    
    # 모든 원소를 차례대로 힙에 삽입(부호를 변경하여)
    for value in iterable:
        heapq.heappush(h, -value)
        
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        result.append(-heapq.heappop(h))
        
    return result
    
result = heapsortDesc([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(result) # [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

 

 

참조

 

https://programmer-ririhan.tistory.com/138

[Python] 힙(heap) 제공 라이브러리 heapq