[백준 2024/02/08] 11279번 최대 힙 - python ver.

https://www.acmicpc.net/problem/11279

11279번: 최대 힙

 

1. 접근 방법

직관적인 문제인 것 같다.

0이 나오면 heappop해서 출력, 비어있다면 0 출력

값이 나오면 heap 에다가 저장.

 

유의해야할 점은 input이 아니라 sys를 이용해야한다는 점이다. input으로 제출을 하니 시간초과가 나왔다.

코드 상으로는 문제가 없다고 확신했기 때문에, sys를 적용하였고 통과할 수 있었다.

 

주의해야할 점은, python의 경우 최소 힙만 지원하기 때문에, heap에 값을 넣어줄 때, -1을 곱해주어야 한다는 점이다.

-1을 곱해서, 최소 힙을 최대 힙처럼 사용하고자 함이다.

 

따라서 출력할 때는 -1을 다시 곱해서 출력해주어야 한다.

(-1*heapq.heappop(max_heap) if max_heap else 0)

 

2. 코드

import heapq
import sys

max_heap = []
for i in range(int(sys.stdin.readline().strip())):
    value = int(sys.stdin.readline().strip())
    if value == 0:
        sys.stdout.write(str((-1*heapq.heappop(max_heap) if max_heap else 0))+'\n')
    else:
        heapq.heappush(max_heap, -1*value)