[힙] 이중 우선순위 큐

문제 설명

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

프로그래머스

문제 풀이

• operation에 따라 삽입/ 최댓값 pop/ 최솟값 pop을 하는 문제
• 각 op에 따라 split로 나눠 준 뒤 각 연산을 수행
• 우선순위 큐로 짬
• heapq 는 push와 동시에 정렬을 수행함 (기본적으로 최대 정렬-최솟값이 맨 앞으로) 
• 파이썬에서 제공하는 heapq의 기본은 최소 힙을 기반으로 하고 있어서 pop을 할 시 최솟값이 나옴
• 최댓값은 큐의 맨 뒤에 있으므로 D 1이면 q.pop()을 수행 
• 주의할 점은, D 연산을 수행 할 시 q가 비워져있으면 에러를 내므로 continue 조건을 달아줘야 함

오답노트

• 정답을 출력할 때, 최댓값을 q[-1]로 했는데 실패했음
• 최소 힙은 부모 노드가 자식 노드보다 작은 것을 유지하는 것이므로 q[0]이 최솟값이 될 순 있어도 q[-1]이 최댓값인 것을 보장하진 않음
• 따라서 최소 힙에서의 최댓값을 찾을려면 모든 요소를 순회 해야함. max(q)로 대체

소스 코드

import heapq

def solution(operations):
    answer = []
    q=[]
    for op in operations:
        a,b = op.split(" ")
        if(a=="I"):
            heapq.heappush(q,int(b))
        elif not q:			#빈 q에서 pop은 에러를 냄
            continue
        elif(b=="-1"):
            heapq.heappop(q)
        else:
            q.pop()
        print(q)
    if not q:
        answer=[0,0]
    else:
        answer=[max(q),q[0]] 	
   
    return answer

if __name__=='__main__':
    t=[]
    for i in range(9):
        t.append(input().rstrip()) 
    solution(t)