사용자 도구

사이트 도구


ps:problems:boj:11279

최대 힙

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

우선순위 큐

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

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

풀이

  • 최소 힙에서 이어지는 문제.
  • python의 heapq는 최솟값 기준으로만 정렬해주므로, 최댓값을 기준으로 하고 싶을때에는 그냥 -1을 곱해서 넣어주면 된다.
  • 삽입과 삭제의 시간 복잡도는 여전히 O(logn)이므로, 전체 시간 복잡도는 O(nlogn)

코드

"""Solution code for "BOJ 11279. 최대 힙".

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

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

토론

댓글을 입력하세요:
T Q​ G B L
 
ps/problems/boj/11279.txt · 마지막으로 수정됨: 2022/07/08 01:42 저자 teferi