[프로그래머스 Lv.3] 이중우선순위큐 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42628

프로그래머스

풀이

Python의 내장 모듈인 heapq를 사용하여 문제를 풀이할 수 있다. heapq는 이진트리 기반의 최소 힙 자료구조를 제공하는 내장 모듈이다.

문제 풀이에서 사용한 heapq의 메서드들을 간단히 설명한 후 코드를 통해 전체적인 풀이를 설명하겠다.

1. heapq.heappush(list, n): 최소 힙(list)에 n을 삽입, 이진트리에 n을 삽입하는 것이므로 O(logN)의 시간 복잡도를 가짐
2. heapq.heappop(list): 최소 힙(list)에서 루트에 위치한 값인 최솟값을 pop, 마찬가지로 O(logN)의 시간복잡도를 가짐
3. heapq.heapify(list): 일반 배열(list)를 최소 힙으로 변경, 모든 원소들을 heap에 넣기 위해 처리하는 것이므로 O(N)의 시간복잡도를 가짐
4. heapq.nlargest(n, list): 최소 힙(list)에서 큰 순서대로 n개를 반환

이렇게 위의 4가지 heapq 내장 모듈의 메서드들을 사용하여 문제를 풀었다.

import heapq

def solution(operations):
    heap = [] # 최소 힙으로 사용할 변수 선언
    
    for operation in operations:
        op, num = operation.split() # 연산자(알파벳)과 숫자로 split
        
        if op == "I": # 추가 명령일 때는
            heapq.heappush(heap, int(num)) # heappush를 사용하여 최소 힙에 값 삽입
        
        else: # 삭제 명령일 때는
            if heap: # 최소 힙이 비지 않았다면
                if num == '1': # 최댓값 삭제
                    heap = heapq.nlargest(len(heap), heap)[1:] # nlargest를 사용 후 0번째 값을 빼도록 슬라이싱하여 최댓값 제거
                    heapq.heapify(heap) # 다시 최소 힙으로 변경
                else: # 최솟값 삭제
                    heapq.heappop(heap) # heappop을 사용하여 최소 힙에서 최솟값(루트) 삭제

    if heap: # 최소 힙이 비어있지 않았을 경우
        return [heapq.nlargest(1, heap)[0], heap[0]
    return [0,0]

heapq를 사용하기에 최소 힙을 쉽게 사용할 수 있어서 비교적 어렵지 않았다. 하지만 최솟값 삭제와 다르게 최댓값 삭제는 한 번도 사용해보지 못한 nlargest라는 새로운 메서드를 사용해야 했기에 익숙지 않아 어려웠다.