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

1일 1PS 90일차!

📚 문제

---

[Level 3] - 이중우선순위큐

💡 풀이 과정

---

• 이중우선순위큐란
  • 최소힙, 최대힙을 모두 수행할 수 있는 큐이다.
• 실제 하나의 큐로 최대, 최소를 O(1) 로 찾아낼 수는 없다.
• 여기에서는 결국 최대힙, 최소힙 두 개를 사용해야한다.
• 문제의 조건이 매우 허술하다.
  • 실제 배열에 max(answer), min(answer) 로도 통과 될 정도로 허술한 테스트 케이스이다.
  • 넉넉한 시간으로 minHeap, maxHeap 에서 pop 하며 매번 동기화를 위해 같은 값을 없애주었다.
  • 이때 remove 시 heap 구조가 깨질 수 있으므로 heapify 를 통해 다시 힙 구조를 맞춰주어야한다.
    • 이 과정 없다면 실제 일부 테스트케이스에서 오답이 발생한다.
• 하지만 이 부분도 remove, heapify 는 쓸데없는 연산이다.
  • 어짜피 서로 가장 관계 없는 값들을 지워나가는 것이기 때문에 length 만을 유지하고 만약 0 이 된다면 이때만 두 배열을 초기화해주면 된다.

📌포인트

---

• 테스트케이스가 허술하더라도 제대로 코딩하자.

💻 코드

---

import heapq

def solution(operations):
    minHeap = []
    maxHeap = []
    length = 0

    for op in operations:
        i, num = op.split()
        num = int(num)

        if i == 'I':
            heapq.heappush(minHeap, num)
            heapq.heappush(maxHeap, -1 * num)
            length += 1
        elif i == 'D' and num == 1:
            if maxHeap:
                maxNum = -1 * heapq.heappop(maxHeap)
                # minHeap.remove(maxNum)
                # heapq.heapify(minHeap)
                
                length -= 1
        elif i == 'D' and num == -1:
            if minHeap:
                minNum = heapq.heappop(minHeap)
                # maxHeap.remove(-1 * minNum)
                # heapq.heapify(maxHeap)
                
                length -= 1

        if length <= 0:
            minHeap, maxHeap = [], []


    if minHeap:
        maxNum = -1 * heapq.heappop(maxHeap)
        minNum = heapq.heappop(minHeap)
        return [maxNum, minNum]

    return [0, 0]