테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 최소 힙 ======

===== 풀이 =====
  * 그냥 기본적인 [[ps:우선순위큐]]문제. 
  * heapq 모듈을 이용해서 구현하면 된다.
  * 삽입과 삭제의 시간 복잡도는 O(logn)이므로, 전체 시간 복잡도는 O(nlogn)
  * [[ps:problems:boj:11279]]는 동일한 문제에서 비교 기준이 최댓값으로 바뀐 문제인데, 난이도가 실버 2로 한단계 낮게 잡혀있다. 파이썬 기준으로는 heapq모듈의 디폴트가 최소힙이므로 이 문제가 더 쉬워야 맞지만, c++에서는 라이브러리에서 제공하는 힙의 디폴트가 최대힙으로 되어있기 때문에 그쪽을 기준으로 반영된것 같다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 1927. 최소 힙".

- Problem link: https://www.acmicpc.net/problem/1927
- Solution link: http://www.teferi.net/ps/problems/boj/1927

Tags: [Heap]
"""

import heapq
import sys


def main():
    N = int(sys.stdin.readline())
    heap = []
    for _ in range(N):
        x = int(sys.stdin.readline())
        if x == 0:
            print(heapq.heappop(heap) if heap else '0')
        else:
            heapq.heappush(heap, x)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:실버_1}}