[코드트리 조별과제] 6회차 6회차(8/19 ~ 8/25)

6주 차는 PQ(Priority Queue)에 대해 학습했습니다.

 

해당 자료구조에 대해 개념적으로 이해하고 있고 문제를 풀 때, 탐색 시간을 최적화할 때 사용할 수 있는 것도 알고 있지만 해당 유형의 문제를 많이 풀지 않았다 보니, 문제를 풀 때 쉽게 떠올리지 못해 연습하는 시간을 가졌습니다.

 

파이썬의 경우, 자바와 달리 우선순위 큐가 라이브러리로 구현되어 있지 않기 때문에 우선순위 큐의 연산을 구현할 수 있는 heapq 라이브러리를 사용해 문제를 풀 수 있습니다.

 

heapq는 이진트리로 구현된 자료구조로 값의 삽입 및 삭제 연산의 시간복잡도를 O(log n)으로 수행할 수 있습니다.

 

https://www.codetree.ai/missions/8/problems/process-numeric-commands-6?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

heapq 사용을 익힐 수 있는 기본적인 문제입니다. 파이썬의 heapq는 minium heap이므로 maximum heap을 구현하기 위해서는 삽입할 때 값을 음수로 두어 처리해야 합니다.

 

삽입할 때, 음수 그 자체 값을 삽입하고, 제거할 때 반환되는 값에 다시 음수를 곱해 출력하는 방법도 있지만, 저는 삽입할 때 음수값과 원본값을 튜플을 통해 하나로 묶어 처리하였습니다.

 

값을 묶어서 처리하게 되면, 특정 우선순위를 처리해야 하는 상황에서 튜플의 요소를 순서대로 고려하게 됩니다. 즉 첫 번째 요소와 같은 우선순위인 값이 2개 이상이라면 다음 요소를 통해 우선순위를 결정하게 됩니다.

import heapq

n = int(input())
cmd = [input().split() for _ in range(n)]
hq = []

for c in cmd:
    if c[0] == "push":
        heapq.heappush(hq, (-int(c[1]), int(c[1])))
    elif c[0]  == "pop":
        print(heapq.heappop(hq)[1])
    elif c[0] == "size":
        print(len(hq))
    elif c[0] == "empty":
        print(0 if len(hq) else 1)
    else:
        print(hq[0][1])