[백준 11279] 최대 힙 (Feat.Python)

문제

널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

 

풀이

• 위 문제를 보고 heapq 라이브러리를 사용

import heapq
import sys

input = sys.stdin.readline
N = int(input())
heap = []

for _ in range(N):
    a = int(input())
    if a:
        heapq.heappush(heap, -a)
    else:
        if len(heap):
            print(-(heapq.heappop(heap)))
        else:
            print(0)

 

• 처음에 input = sys.stdin.readline 을 하지않고 입력을 받았으나 지속적인 시간 초과
  • 그냥 input()으로 입력을 받을 경우
    • prompt message를 받고 => 입력받은 값의 개행문자(엔터값)을 삭제하고 반환 [이러한 동작을 하기 때문에 오래 걸림]
  • sys.stdin.readline의 경우 문자열로 입력을 받기만 하기때문에 input() 보다 더 빠른 동작 [시간초과 문제 해결]
• heapq 라이브러리 사용법
  • heapq.heappush({리스트}, {데이터}) : 선언된 리스트를 heap 자료구조와 같은 형태로 추가
  • heapq.heappop({리스트}) : 선언된 리스트에서 가장 작은 값을 반환해주고 리스트에서 값을 삭제
• heapq에서는 Min-Heap을 지원하고 있었기 때문에 본인은 정수값을 음수로 바꿔서 heap에 넣어주었고 이를 다시 양수로 바꿔서 꺼내주는 방식으로 Max-Heap 을 구상 및 구현