[프로그래머스/Python] 이중우선순위큐

 

 

1. 프로그래머스 이중우선순위큐(lv.3)

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

프로그래머스

 

풀이

 

CODE

import heapq

def solution(operations):
    heap = []
    for each in operations:
        # 삽입
        if each[0] == 'I':
            heapq.heappush(heap,  int(each[2:]))
        # 최솟값 삭제
        elif len(each) == 4:
            if heap:
                heapq.heappop(heap)
        # 최댓값 삭제
        else:
            if heap:
                heap.pop()

    answer = []
    if heap:
        answer.append(max(heap))
        answer.append(min(heap))
    else:
        answer.append(0)
        answer.append(0)
        
    return answer

• 기본을 놓치지 않는 게 제일 중요하다... 라는 걸 배운 문제
  
  • 최소힙에서 최댓값을 어떻게 삭제하지? 에 갑자기 멘붕이 와서 고민에 빠졌는데,
    heqp은 결국 리스트이고 현재 자동 오름차순 정렬이 되고 있는 중이므로 pop을 통해 간단히 해결할 수 있는 거였다.
  • 너무 어렵게 생각하면 독이 되는 것 같다.
• +++++ 이 문제는 testcase가 매우 적었어서 운좋게 통과된 것이었다. 원래는 pop()을 하면 힙은 트리 자료구조이기 때문에 최솟값은 보장하지만, 최댓값은 항상 끝에 있다고 보장하지 않는다. 따라서 따로 정렬을 하거나, 두 개의 힙을 사용하는 등 최댓값을 뽑기 위한 다른 로직이 필요하다.