이중우선순위큐

• BOJ의 이중 우선순위 큐와 동일한 문제. 풀이는 그쪽 참고
• 다른 사람의 코드를 보면, O(n^2) 풀이로도 통과되는 것은 BOJ와 마찬가지인데, 그 외에도 제대로 동작하지 않는 코드들도 통과된 것들이 보인다. 테스트케이스가 약한것 같다.

"""Solution code for "Programmers 42628. 이중우선순위큐".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42628
- Solution link: http://www.teferi.net/ps/problems/programmers/42628
"""

from teflib import priorityqueue


def solution(operations):
    max_heap = priorityqueue.UpdatableHeap()
    min_heap = priorityqueue.UpdatableHeap()
    for op in operations:
        cmd, n = op.split()
        if cmd == 'I':
            num = int(n)
            max_heap.push(-num)
            min_heap.push(num)
        elif max_heap.size():
            if n == '1':
                num = -max_heap.pop()
                min_heap.delete(num)
            else:
                num = min_heap.pop()
                max_heap.delete(-num)
    if max_heap.size() == 0:
        return [0, 0]
    else:
        return [-max_heap.top(), min_heap.top()]

• Dependency: teflib.priorityqueue.UpdatableHeap