사용자 도구

사이트 도구


ps:problems:boj:1927

최소 힙

ps
링크acmicpc.net/…
출처BOJ
문제 번호1927
문제명최소 힙
레벨실버 1
분류

우선순위 큐

시간복잡도O(nlogn)
인풋사이즈n<=100,000
사용한 언어Python
제출기록35124KB / 148ms
최고기록120ms
해결날짜2021/07/12
태그

[단계별]22단계, [라이]우선순위 큐

풀이

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

코드

"""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()

토론

댓글을 입력하세요:
A U P W D
 
ps/problems/boj/1927.txt · 마지막으로 수정됨: 2022/07/08 01:44 저자 teferi