[Python] 이중우선순위큐

1. 문제

 

 

 

2. 풀이 과정

방법 1) remove하면 heap구조가 깨지지만 잘 작동한다. 이유는 최댓값을 빼서 구조가 깨진 후, min_h에서 pop하거나 push할 때 다시 heap 구조를 만들기 때문이다.

따라서, 작동하는 데에는 문제가 없지만 max값을 찾는 데에서 시간이 비교적 많이 걸린다. 

import heapq as hq
def solution(operations):
    answer = [0, 0]
    min_h = [] #기본
    
    for operation in operations:
        order, num = operation.split()
        num = int(num)
        if order == 'I':
            hq.heappush(min_h, num)
        elif min_h and order == 'D':
            if num == 1:
                min_h.remove(max(min_h))
            else:
                hq.heappop(min_h)
    if min_h:
        answer = [max(min_h), min_h[0]]
                
    return answer

 

방법 2) min_h과 max_h을 따로 쓰고 delete하고 결과를 출력할 때 동기화시킨다.

동기화 방법 : 다른 heap에 있는 값이 나올 때까지 pop을 진행한다. 두 heap이 완전 같지는 않지만, 삽입, 삭제할 때 두 heap 모두에 있는 데이터만 취급되기 때문에 오류 없이 돌아간다.

 

아래는, 중복된 값이 들어왔을 때도 정상적으로 작동하는지 테스트하기 위해 직접 추가한 케이스이다.

추가해본 테스트 케이스 : ["I 2", "I 2", "I 10", "D -1", "I 1", "I -3", "D 1", "D 1"]

기댓값 : [1, -3]

*프로그램의 테스트 케이스가 부족한 것 같다. 개인적으로 테스트 케이스를 늘려서 해봤지만, 고려하지 못한 부분 있을 수 있다.

import heapq as hq
def next_v(h1, h2):#h1에서 빼기
    while h1:
        temp = h1[0]
        if -temp in h2:
            #같은 값이 여러 개 있을 수 있음
            #갯수 맞춰주기
            for _ in range(h1.count(temp) - h2.count(-temp) + 1):
                hq.heappop(h1)
            return temp
    return 0
    
def solution(operations):
    min_h = [] #기본
    max_h = []
    
    for operation in operations:
        order, num = operation.split()
        num = int(num)
        if order == 'I':
            hq.heappush(min_h, num)
            hq.heappush(max_h, -num)
        elif order == 'D':
            if num == 1:
                next_v(max_h, min_h)
                if not max_h: #max_h이 비었으면
                    min_h = []
            else:
                next_v(min_h, max_h)
                if not min_h: #min_h이 비었으면
                    max_h = []
    
    return [-next_v(max_h, min_h), next_v(min_h, max_h)]