사용자 도구

사이트 도구


ps:problems:boj:7662

이중 우선순위 큐

ps
링크acmicpc.net/…
출처BOJ
문제 번호7662
문제명이중 우선순위 큐
레벨골드 5
분류

우선순위큐

시간복잡도O(nlogn)
인풋사이즈n<=1,000,000
제출기록128892KB / 5644ms
최고기록3156ms
해결날짜2021/05/14

풀이

  • Double-ended priority queue 를 만드는 문제.
  • 링크에서 설명했듯이 다양한 방법이 있지만, 여기에서는 가장 심플한 방법인 min heap과 max heap을 UpdatableHeap로 만들어서 사용했다.
  • n번의 삽입 삭제가 일어날때, 각각은 O(logn)에 처리되니 총 시간 복잡도는 O(nlogn).
  • 그러나 실제 제출된 코드들을 보면, 그냥 deque를 정렬된 상태로 유지해서, 삽입을 O(n)으로 처리하는 코드가 시간복잡도는 느리지만 더 빠르게 동작했다.;

코드

"""Solution code for "BOJ 7662. 이중 우선순위 큐".

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

import sys
from teflib import priorityqueue


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        max_heap = priorityqueue.UpdatableHeap()
        min_heap = priorityqueue.UpdatableHeap()
        k = int(sys.stdin.readline())
        for _ in range(k):
            op, n = sys.stdin.readline().split()
            if op == 'I':
                num = int(n)
                max_heap.push(-num)
                min_heap.push(num)
            elif max_heap:
                if n == '1':
                    num = -max_heap.pop()
                    min_heap.delete(num)
                elif n == '-1':
                    num = min_heap.pop()
                    max_heap.delete(-num)
        if max_heap:
            print(-max_heap.top(), min_heap.top())
        else:
            print('EMPTY')


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
P᠎ B G W M
 
ps/problems/boj/7662.txt · 마지막으로 수정됨: 2022/06/29 02:34 저자 teferi