Lv3. 이중우선순위 큐

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/42628

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

 

#1. 설계 및 풀이

1. operations 동안 반복

 

2. I : 삽입

D 1 : max heap (큐를 음수화시킨 후 heap으로 만들기-> 연산 후에 다시 음수화시켜서 원래대로 만들기)

D -1 : min heap (파이썬 heapq 기본)

 

3. 끝났는데 큐 길이 == 0: [0, 0] 리턴

아니면 min heap -> 최솟값

max heap -> 최댓값 구해서 대입 후 리턴

 

 

- 사실 operations 길이도 최대 백만개로 나와있고,

물론 힙의 시간복잡도가 NlogN이라서 2000만이 간신히 되긴 하지만 

중간에 큐를 음수화시키는 과정도 있기도 하고 사실 아슬아슬하다고 생각하고 제출했는데 맞아서 놀랐다.

 

아마 테스트케이스가 몇개 없어서 통과한 것 같다.

 

import heapq

def solution(operations):
    answer = [0, 0]
    q = []
    
    for op in operations :
        order, num = op.split()
        num = int(num)
        if order == 'I' : # 삽입
            q.append(num)
            
        else : # 삭제
            if len(q) == 0 :
                continue
            if num == -1 : # min heap
                heapq.heapify(q)
                v = heapq.heappop(q)
            else : # max heap
                for i in range(len(q)) :
                    q[i] = -q[i]
                heapq.heapify(q)
                v = heapq.heappop(q)
                for i in range(len(q)) :
                    q[i] = -q[i]
                    
    if len(q) == 0 : # 큐 비어있으면 무시
        return answer
    else :
        heapq.heapify(q)
        answer[1] = heapq.heappop(q)
        for i in range(len(q)) :
            q[i] = -q[i]
        heapq.heapify(q)
        answer[0] = -heapq.heappop(q)
            
    return answer