사용자 도구

사이트 도구


ps:problems:programmers:42628

이중우선순위큐

ps
링크programmers.co.kr/…
출처프로그래머스
문제 번호42628
문제명이중우선순위큐
레벨Level 3
분류

우선순위큐

시간복잡도O(nlogn)
인풋사이즈n<=1,000,000
사용한 언어Python
해결날짜2021/05/14
태그

고득점 Kit - 힙(Heap)

풀이

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

토론

댓글을 입력하세요:
U C L Q A
 
ps/problems/programmers/42628.txt · 마지막으로 수정됨: 2021/05/28 03:11 저자 teferi