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

문제

풀이

파이썬의 우선순위 큐는 기본적으로 최소 힙이므로, 튜플로 (-num,num)을 입력하여 최대 힙을 따로 구현해주었다.

그런 후 최소값을 삭제할 때는 최소 힙에서 최소값을 반환하여, 최대 힙에서 삭제해 주고,

최대값을 삭제할 때는 최대 힙에서 최댓값을 반환하여 최소 힙에서 삭제해 주었다.

정답은 맞았지만 계산해보니 최대 경우의 수가 50만개를 삽입하고 50만개를 삭제할때

50만개의 등차수열만큼 시간이 걸린다고 생각이 되었다.

아마 프로그래머스에 테스트케이스가 널널하게 계산되어있는거 같다. 추가로 최적화 작업을 해봐야겠다.

 

코드

import heapq
def solution(operations):
    max_heap=[]
    min_heap=[]
    count= 0
    for i in operations:
        op,num = i.split(" ")
        if op=="I":
            heapq.heappush(max_heap, (-int(num),int(num)))
            heapq.heappush(min_heap, int(num))
            count+=1
        elif op=="D":

            if num=="1" and count>0:
                del_num = heapq.heappop(max_heap)[1]
                min_heap.remove(del_num)
                count-=1
            elif num =="-1" and count > 0:
                del_num = heapq.heappop(min_heap)
                max_heap.remove((-del_num,del_num))
                count-=1
    answer = []
    if count>0:
        answer.append(heapq.heappop(max_heap)[1])
        answer.append(heapq.heappop(min_heap))
    else:
        answer= [0,0]
    return answer