[백준 11279] 최대 힙 - 파이썬

백준 11279 - 최대 힙

---

* 풀이과정

파이썬 내장 모듈 heapq을 이용하면 풀 수 있는 문제이다.

 

1) heapq은 기본적으로 최소 힙 기능을 제공하므로, 입력받은 값의 부호를 바꿔 리스트에 저장

2) 입력받은 숫자가 0일 때, heap.heapop()의 부호를 바꿔 출력

import sys
import heapq as hq

N = int(input())
heap = []

for i in range(N):
    x = int(sys.stdin.readline())
    # x가 자연수인 경우, -x 값을 heappush
    if x>0:
        hq.heappush(heap, -x)
    
    # x가 0인 경우
    else:
    	# heap 리스트가 비어있지 않다면, heappop(heap) 값의 부호를 바꿔 출력
        if heap: print(-hq.heappop(heap))
        # heap 리스트가 비어있다면, 0 출력
        else: print(0)

---

익숙한 input()형식으로 입력받았더니, 시간초과 문제가 발생하였다.

sys.stdin.readline()으로 입력받아, 시간초과 문제가 해결되었다.

input()은 prompt message를 출력하고, 개행 문자를 삭제한 값을 리턴한다는 점에서 상대적으로 느리기 때문이다.

 

input()

• prompt message를 인수로 받을 수 있다. (없는 경우에도, 약간의 부하로 작용 가능)
• 입력받은 값의 개행 문자를 삭제하여 리턴한다. (rstript() 함수를 적용)

sys.stdin.readline()

• prompt message를 인수로 받지 않는다.
• 개행문자를 포함한 값을 리턴한다.