[ Lv 3 ] 이중우선순위큐

풀이 과정

---

1. 최소 히프, 최대 히프를 둔다.
2. 데이터 삽입 시 최소히프, 최대히프에 모두 저장하면서 동시에 index도 같이 둔다.
3. 데이터 삭제
   • 최솟값 삭제하는 경우에는 최소히프에서 삭제 및 index 저장
   • 최댓값 삭제하는 경우에는 최대히프에서 삭제 및 index 저장
   • 삭제하기 전에 히프에서 이미 삭제된 index인지 검사하는 과정 추가
4. 히프가 비어있다면 [0, 0]을, 히프가 비어있지 않다면 [최대히프의 맨 위, 최소히프의 맨 위] 출력

소스 코드

import heapq
def solution(operations):
    answer = []
    max_heap = []
    min_heap = []
    remove_set = set()
    index = 0
    for op in operations:
        temp = op.split()
        operation = temp[0]
        number = int(temp[1])
        if operation == 'I':
            heapq.heappush(min_heap, [number, index])
            heapq.heappush(max_heap, [-number, index])
            index += 1
        elif operation == 'D':
            if number == -1:
                while min_heap:
                    number, idx = heapq.heappop(min_heap)
                    if idx not in remove_set:
                        remove_set.add(idx)
                        break

            elif number == 1:
                while max_heap:
                    number, idx = heapq.heappop(max_heap)
                    if idx not in remove_set:
                        remove_set.add(idx)
                        break

    while min_heap:
        if min_heap[0][1] in remove_set:
            heapq.heappop(min_heap)
        else:
            break

    while max_heap:
        if max_heap[0][1] in remove_set:
            heapq.heappop(max_heap)
        else:
            break

    if len(min_heap) == 0:
        return [0, 0]
    else:
        return [-max_heap[0][0], min_heap[0][0]]
    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges