사용자 도구

사이트 도구


ps:problems:boj:11286

절댓값 힙

ps
링크acmicpc.net/…
출처BOJ
문제 번호11286
문제명절댓값 힙
레벨실버 1
분류

우선순위 큐

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

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

풀이

  • 이번에는 절댓값을 키값으로 갖는다. 절댓값과 원래값을 튜플로 묶어서 heapq 모듈을 사용하도록 하자.
  • 삽입과 삭제의 시간 복잡도는 여전히 O(logn)이므로, 전체 시간 복잡도는 O(nlogn)

코드

"""Solution code for "BOJ 11286. 절댓값 힙".

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

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)[1] if heap else '0')
        else:
            heapq.heappush(heap, (abs(x), x))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
Z H I L J
 
ps/problems/boj/11286.txt · 마지막으로 수정됨: 2022/07/08 01:43 저자 teferi