[99클럽 코테 스터디 10일차 TIL] 이중우선순위큐

문제

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

제한사항

operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.

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

입출력 예

operations return

["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"]	[0,0]
["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"]	[333, -45]

입출력 예 설명

입출력 예 #1

• 16과 -5643을 삽입합니다.
• 최솟값을 삭제합니다. -5643이 삭제되고 16이 남아있습니다.
• 최댓값을 삭제합니다. 16이 삭제되고 이중 우선순위 큐는 비어있습니다.
• 우선순위 큐가 비어있으므로 최댓값 삭제 연산이 무시됩니다.
• 123을 삽입합니다.
• 최솟값을 삭제합니다. 123이 삭제되고 이중 우선순위 큐는 비어있습니다.

따라서 [0, 0]을 반환합니다.

입출력 예 #2

• 45와 653을 삽입후 최댓값(653)을 삭제합니다. -45가 남아있습니다.
• 642, 45, 97을 삽입 후 최댓값(97), 최솟값(-642)을 삭제합니다. -45와 45가 남아있습니다.
• 333을 삽입합니다.

이중 우선순위 큐에 -45, 45, 333이 남아있으므로, [333, -45]를 반환합니다.

 

키워드

• 힙

 

주요 개념

• heapq 모듈에서 heappop()으로 최소값을 찾을 수 있지만 다른 방법도 있다.
• 다음 함수를 통해 최대/최소 값을 찾을 수 있다.
  • heapq.nlargest(n, iterable, key=None)
  • heapq.nsmallest(n, iterable, key=None)
• 최소 힙에서 최대값을 삭제하는 방법
  

  heap = heapq.nlargest(len(heap), heap)[1:]
  heapq.heapify(heap)

  
  
  • 위의 코드는 heap에서 len(heap)개의 가장 큰 수를 내림차순으로 뽑아낸다.
  • 그리고 가장 큰 수를 삭제하기 위해서는 [1:] 로 슬라이싱하면 된다.
  • 다시 최소힙으로 만들려면 heapify()을 사용하면 된다.
• ex)
  

  import heapq
  
  heap = [5, 3, 9, 2, 6]
  heapq.heapify(heap)
  print(heap) # [2, 3, 9, 5, 6]
  
  heap = heapq.nlargest(len(heap), heap)[1:]
  print(heap) # [6, 5, 3, 2]
  
  heapq.heapify(heap)
  print(heap) # [2, 5, 3, 6]

 

해결 방법

풀이

import heapq
def solution(operations):
    answer = []
    heap = []
    heapq.heapify(heap)
    for i in operations:
        if i.startswith('I'):
            heapq.heappush(heap, int(i[2:]))
        elif len(heap) != 0 and i == "D 1":
            heap = heapq.nlargest(len(heap),heap)[1:]
            heapq.heapify(heap)
        elif len(heap) != 0 and i == "D -1":
            heapq.heappop(heap)
    if len(heap) == 0:
        answer = [0, 0]
    else:
        answer = [max(heap), min(heap)]
    
    return answer