백준 큐 11286번

안녕하세요, GDSC 웹 멤버 오정인입니다.
우선순위큐의 세번째 문제를 풀어봤습니다!

우선순위 큐

우선순위 큐는 우선순위의 개념을 큐에 도입한 자료 구조이며 이는 배열, 연결리스트, 힙으로 구현이 가능합니다. 이 중 힙(Heap)을 이용해서 구현하는 것이 가장 효율적이라고 합니다.(O(logn))

힙(heap)

완전 이진 트리의 일종으로 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 자료구조입니다. 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙을 ‘최대 힙’, 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙을 ‘최소 힙’ 이라고 합니다. 키값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립하며, 특히 형제 사이에는 대소관계가 정해지지 않습니다.

heapq

heapq 모듈은 이진 트리 기반의 최소 힙(min heap) 자료구조를 제공합니다.

heapq 활용

heapq.heappush(heap, item) : item을 heap에 추가
item이 튜플일경우: 튜플의 첫번째 요소는 우선순위 값, 두번째 요소는 데이터
heapq.heappop(heap) : heap에서 가장 작은 원소를 pop
heapq.heapify(x) : 리스트 x를 힙으로 변환

풀이

import sys
import heapq

n=int(sys.stdin.readline().rstrip())
heap=[]
for _ in range(n):
    tmp=int(sys.stdin.readline())
    if tmp==0:
        try:
            result=heapq.heappop(heap)
            print(result[1])
        except:# heap이 비어있을경우 0 출력
            print(0)
    else:
        heapq.heappush(heap, (abs(tmp),tmp))#절대값을 구해주는 abs

마무리

저는 heapq도 처음 써봤네요,,, heapq를 어떻게 쓰는지 알고 있었으면 쉽게 풀 수 있는 문제 같습니다.