프로그래머스(programmers) 이중순위우선큐 python 정답 [힙(heap)]

프로그래머스(programmers) 이중순위우선큐 python 정답 [힙(heap)]

문제 링크

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

프로그래머스

 

문제 정답

입출력 예

operations	return
["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"]	[0,0]
["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"]	[333, -45]

정답 코드

import heapq
def solution(operations):
    opsList = list(map(lambda x: x.split(" ") ,operations))
    answer = []    
    for opsItem in opsList:
        ops,item = opsItem
        if ops =='I':
            heapq.heappush(answer,int(item))             
        if ops == "D" and item =='1':
            if not answer : continue
            maxItem = max(answer)
            answer.remove(maxItem)
        if ops == "D" and item =='-1':
            if not answer : continue
            heapq.heappop(answer)
    if not answer :
        return [0,0]
    return [max(answer),answer[0]]

    return answer

문제 해설

1. 힙에 넣는건 일반적인 heappush다.
2. 힙에서 삭제할 때
   1. 힙의 크기가 0이면 넘어간다.
   2. 힙에서 해당 아이템을 제거한다.
3. 다 처리하고 모든 아이템이 삭제되었으면  [0, 0] 리턴

삭제가 시간복잡도 n이 되는데, 힙은 최소힙 혹은 최대 힙이므로 이 이상 최적화 할 수 있는 방법은 없어보인다.

만약 방법이 있다면 알려달라.