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

코드

from heapq import *
def solution(operations):
    q = []
    for i in operations:
        op, n = i.split()
        if op == 'I':
            heappush(q, int(n))
        elif op == 'D' and len(q) != 0:
            if n == "-1":
                heappop(q)
            else:
                q.sort()
                q.pop()
    if q:
        return [max(q), q[0]]
    else:
        return [0,0]

max가 리프 노드에 있다는 것은 보장되지만 가장 끝 노드(인덱스)에 있다는 것은 보장되지 않기 때문에 q.sort() 해줌

최대값 뺄 때 q.sort() 했는데 트리 구조가 안무너지네

왜 다 통과하지

..?

heappop, heappush 할 때 트리구조를 되찾는건지 아니면 테케가 부족해서 운좋게 통과한건지 몰겠슴

 

의문 해결 과정 

https://github.com/lake041/sesac-algorithm/issues/1

[프로그래머스] 이중우선순위큐 질문 · Issue #1 · lake041/sesac-algorithm

 

 

뭔가 이 문제에서 실질적으로 원한건 max_heap, min_heap 이렇게 heapq를 2개를 만들어서 동기화해가면서 푸는 방법이였을 것 같은데 동기화 방법이 마땅히 떠오르지 않음

문제 자체가 테케가 많이 부족해서 정확하게 맞는지도 모르겠음

일단 통과하긴 하는데 ..

from heapq import heappush, heappop

def solution(operations):
    maxq, minq = [], []
    deleted_index = []

    for i in range(len(operations)):
        op, num = operations[i].split()
        num = int(num)
        if op=="I":
            heappush(maxq, (-num, i))
            heappush(minq, (num, i))
        elif num == 1:
            if maxq:
                _, index = heappop(maxq)
                deleted_index.append(index)
        elif num == -1:
            if minq:
                _, index = heappop(minq)
                deleted_index.append(index)

        while minq and minq[0][1] in deleted_index:
            heappop(minq)
        while maxq and maxq[0][1] in deleted_index:
            heappop(maxq)
                
    return [-heappop(maxq)[0], heappop(minq)[0]] if maxq else [0, 0]

이게 정석 풀이인듯 ?