[프로그래머스] LEVEL3 이중우선순위큐, python

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

코딩테스트 연습 - 이중우선순위큐

from heapq import heappush, heappop

def solution(operations):
    answer = [0, 0]
    min_h, max_h = [], []
    number_in_heap = dict()
    for op in operations:
        if op[0] == 'I': # 숫자 삽입
            _, num = op.split()
            num = int(num)
            heappush(min_h, num)
            heappush(max_h, -num)
            if not number_in_heap.get(num):
                number_in_heap[num] = 0
            number_in_heap[num] += 1
        else:
            if op[2] == '1': # 최댓값 삭제
                while max_h:
                    tmp_number = -heappop(max_h)
                    if number_in_heap[tmp_number]:
                        number_in_heap[tmp_number] -= 1
                        break
            else: # 최솟값 삭제
                while min_h:
                    tmp_number = heappop(min_h)
                    if number_in_heap[tmp_number]:
                        number_in_heap[tmp_number] -= 1
                        break

    while min_h:
        tmp_number = heappop(min_h)
        if number_in_heap[tmp_number]:
            answer[1] = tmp_number
            break
    while max_h:
        tmp_number = -heappop(max_h)
        if number_in_heap[tmp_number]:
            answer[0] = tmp_number
            break

    return answer

이중 우선순위큐는 백준에서도 한번 풀어봤던 문제이다.

그당시에는 많이 어려웠었는데 지금은 그때보단 쉽게 푼거같다. 

 

이중 우선순위큐를 만들기 위해서 최대힙과 최소힙을 만든다.

heapq라는 내장 라이브러리를 사용하면 최소 힙을 사용할수 있는데 값을 추가할때 마이너스(-) 값으로 넣고 뺄때 다시 되돌리면 최대힙으로 사용할수 있다.

그리고 최대힙과 최소힙을 동기화하는 과정이 필요하다.

heap이라는 자료구조에선 push와 pop만 가능한데 동기화를 위해 딕셔너리를 하나 생성했다.

어떤 값이 들어오고 나가는지 카운트 하기 위함이고, 힙에서 제거할때 딕셔너리 값이 0인 경우 이미 빠진 값이라고 체크하기 위함이다. 

operation이 다 끝난 이후에도 동기화를 한번더 진행해서 딕셔너리에 0 이상인 값인 경우에만 answer를 갱신하면 된다.