프로그래머스 이중우선순위큐 파이썬

프로그래머스 파이썬 이중우선순위큐 프로그래머스 이중우선순위큐 파이썬 파이썬 프로그래머스 이중우선순위큐 파이썬 이중우선순위큐 프로그래머스 이중우선순위큐 프로그래머스 파이썬 이중우선순위큐 파이썬 프로그래머스

이중우선순위큐

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

문제 단순화

• "I 숫자", "D 1", "D -1" 의 문자열 명령어를 통해서 숫자삽입, 최댓값 삭제, 최소값 삭제가 수행된다.
• 명령어 수행 후, 큐가 비어 있으면 [0,0]을 리턴하고 비어 있지 않으면 [최댓값, 최소값]을 리턴한다.
• 삭제할 요소가 없는 경우 무시한다. (제약조건)

문제풀이

• 최소힙, 최대힙으로 최소값, 최대값을 찾는다.

    min_heap[0] = min_value
    max_heap[0] = max_value

    I value : 
        min_heap, max_heap에 각각 value를 추가
    D 1 :
        max_heap에서 pop
    D -1 :
        min_heap에서 pop

    이중우선순위큐의 min_value은 항상 max_value보다 작거나 같아야 하므로 min_heap[0] <= max_heap[0] 를 만족해야 한다.

    따라서 min_heap[0] > max_heap[0] 인 경우, 이중우선순위큐는 성립하지 않으므로 heap을 초기화한다.

팁

• 코드 작성 시, 구현 우선순위를 설정하여 진행하는 게 좋다. ex) 제약조건

코드

import heapq as hq

def solution(operations):
    answer = [0,0]
    min_heap = []
    max_heap = []
    for str in operations:
        cmd, num = str.split()
        num = int(num)
        if cmd == 'I':
            hq.heappush(min_heap, (num, num))
            hq.heappush(max_heap, (-num, num))
        elif min_heap:
            if num == 1:
                hq.heappop(max_heap)
            else:
                hq.heappop(min_heap)
            if not min_heap or not max_heap or min_heap[0][1] > max_heap[0][1]:
                min_heap = []
                max_heap = []
    if min_heap:
        answer = [max_heap[0][1],min_heap[0][1]]
    return answer