[PG/Python] 이중우선순위큐

📌 문제

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

코딩테스트 연습 - 이중우선순위큐

 

📌 문제 접근 방법

1. 최대/최소값을 삭제하기때문에 힙을 사용해야 하나? 생각했지만, 힙 하나로 최대/최소값을 삭제하기는 힘들 것 같아서 일단 리스트로 구현을 해봤다. 문제 그대로 삽입/삭제만 했는데도 시간초과없기 통과가 되었지만, 문제에서 요구하는 풀이는 아닐 것 같아서 다른 풀이를 참고했다.
2. 힙을 하나만 사용하지 않고 최대힙, 최소힙을 모두 사용하면 내가 처음에 생각했던대로 구현이 가능했다.
3. 대신 두 힙에는 같은 값이 중복으로 저장되어있으므로 최대힙, 최소힙 중 하나라도 비게 된다면 두 힙 모두 비게 되는 것이다.
4. 또한 최대힙의 최대값보다 최소힙의 최소값이 더 작다면, 모든 값이 삭제된 것으로 판단한다.
   (이건 직접 값을 대입해보면 훨씬 이해가 빠르다.)
5. 2~4의 조건만 추가하여 리스트를 힙으로 바꾸어줬더니 통과할 수 있었다.

 

📌 코드

def solution(operations):
    queue = []
    for operation in operations:
        oper = operation.split()
        
        if oper[0] == 'I':
            queue.append(int(oper[1]))
        elif queue and oper[1] == '1':
            queue.pop(queue.index(max(queue)))
        elif queue:
            queue.pop(queue.index(min(queue)))
            
    answer = [0, 0]
    if queue:
        answer = [max(queue), min(queue)]
        
    return answer

-> 리스트 사용

import heapq

def solution(operations):
    max_heap = []
    min_heap = []
    
    for operation in operations:
        oper = operation.split()
        
        if oper[0] == 'I':
            heapq.heappush(max_heap, -int(oper[1]))
            heapq.heappush(min_heap, int(oper[1]))
        elif max_heap and oper[1] == '1':
            heapq.heappop(max_heap)
            if not max_heap or -max_heap[0] < min_heap[0]:
                max_heap = []
                min_heap = []
        elif min_heap:
            heapq.heappop(min_heap)
            if not min_heap or -max_heap[0] < min_heap[0]:
                max_heap = []
                min_heap = []
            
    answer = [0, 0]
    if max_heap:
        answer = [-max_heap[0], min_heap[0]]
        
    return answer

-> 힙 사용