[프로그래머스/Python] 알고리즘고득점Kit-힙(Heap)-이중우선순위큐

📌 문제링크

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

프로그래머스

 

📌 문제설명 

이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

 

# 제한사항

• operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
• operations의 원소는 큐가 수행할 연산을 나타냅니다.
• 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
• 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

 

 

 

📌 풀이과정

• 최소힙, 최대힙을 따로따로 만들 필요가 없다. 
• 최소힙에서 최댓값을 구할 수 있기 때문 !! 
  • 처음에는 pop(-1)하고 heapify()를 하려 했다. 그런데 이 부분에서 에러가 나는 것 같아 heapq의 함수를 찾아보니 다음과 같은 함수가 있어 정리해보려 한다. 
  • heapq.nlargest(n, iterable, key=None) ==> 최소힙에서 최댓값을 구할 때 사용하기 좋을 것 같다. 
    heapq.nsmallest(n, iterable, key=None)

 

✅ 배운 점 

# heapq.nlargest() 함수 사용법 

• n: 힙을 내림차순으로 정렬해 n개의 데이터를 리턴한다. 
• iterable: heap 이름을 넣으면 된다. 
• 기존의 힙은 변경하지 않는다. 변경된 힙은 리턴하기 때문에 반드시 = 로 받아줘야 한다. 

 

 

📌 풀이코드 

import heapq as hq
def solution(operations):
    answer = []
    for operation in operations: 
        op, v = operation.split()
        if op == "I":
            hq.heappush(answer, int(v))
        elif op == "D" and answer:
            if v == "1":
                answer = hq.nlargest(len(answer), answer)[1:]
                # answer.pop(-1)
                hq.heapify(answer)
            elif v == "-1": hq.heappop(answer)
        
    if answer: return [max(answer), min(answer)]
    else: return [0,0]