[프로그래머스] 이중우선순위큐

문제 링크:

https://school.programmers.co.kr/learn/courses/30/lessons/42628

회고:

• 최댓값과 최솟값을 매번 제거해야 해서 최대힙과 최소힙을 알 수 있는 리스트를 각각 만들었다.
• 힙 구조로 된 리스트에서 중간에 있는 요소를 제거하면 힙 구조가 깨질 가능성이 있을 것 같아, 힙 구조를 재구성하는 heapify 메서드를 추가했는데 O(n)의 시간복잡도를 가져서 리스트가 길어질수록 비례하게 느려질 것 같다.

python

import heapq


def solution(operations: list) -> list:
    """
    operations 설명
    I 숫자: 숫자 추가
    D -1: 최솟값 제거
    D 1: 최댓값 제거
    """
    max_heap = []  # 숫자가 클수록 우선순위 높음
    min_heap = []  # 숫자가 작을수록 우선순위 높음

    for operation in operations:
        oper, num = operation.split()
        num = int(num)

        # 숫자 추가
        if oper == "I":
            heapq.heappush(min_heap, num)
            heapq.heappush(max_heap, -num)
        # 숫자 제거
        elif max_heap and oper == "D":
            # 최솟값 제거
            if num == -1:
                x = -heapq.heappop(min_heap)

                max_heap.remove(x)
                heapq.heapify(max_heap)

            # 최댓값 제거
            elif num == 1:
                x = -heapq.heappop(max_heap)

                min_heap.remove(x)
                heapq.heapify(min_heap)

    max_value, min_value = 0, 0
    if max_heap:
        max_value = -heapq.heappop(max_heap)
        min_value = heapq.heappop(min_heap)

    return [max_value, min_value]


if __name__ == "__main__":
    result = solution(["I 1", "I 2", "D 1", "D -1", "I 3", "I 4", "D 1"])

    print(result)

[3, 3]