[Python] 프로그래머스 Lv3_이중우선순위큐

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

프로그래머스

 

"""
입출력 예시)

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

import heapq

def solution(operations):
    answer = []
    heap = [] # 힙 생성

    for oper in operations:
      if oper[0] == 'I': # 명령어가 'I'인 경우
        heapq.heappush(heap, int(oper[2:])) # 공백 뒤의 숫자를 heap에 삽입 ('I' + (공백) + 숫자)
      
      else: # 명령어가 'D'인 경우
        if len(heap) == 0: # 힙이 비어있으면 pass (-> 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시)
          pass
        elif oper[2] == '-': # 공백 뒤에 '-'가 있는 경우
          heapq.heappop(heap) # heap에서 최솟값을 삭제
        else: # 공백 뒤에 바로 1이 오는 경우
          heap = heapq.nlargest(len(heap), heap)[1:] # heap에서 최댓값을 찾아서 이 최댓값을 제외하고 리스트 힙에 삽입
          heapq.heapify(heap) # 리스트 힙을 heap으로 변환

    if heap: # 힙이 비어있지 않으면
      answer.append(max(heap)) # 최댓값
      answer.append(min(heap)) # 최솟값
    else: # 힙이 비어있으면
      answer.append(0) 
      answer.append(0)

    return answer

 

 

• heapq
  
  • heapq.heappush(heap, item) : item을 heap에 추가
  • heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴, 비어 있는 경우 IndexError
  • heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환
• 힙에서 최댓값 찾기
  • heapq.nlargest(n, iterable, key=None)
• 힙에서 최솟값 찾기
  • heapq.nsmallest(n, iterable, key=None)

 

• heapq 공식 문서

https://docs.python.org/ko/3/library/heapq.html

heapq — 힙 큐 알고리즘 — Python 3.10.6 문서

 

 

 

---

 

• operations=["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"] 의 연산 과정

"""
1) I -45: -45 삽입 -> [-45]
2) I 653: 653 삽입 -> [-45, 653]
3) D 1: 최댓값(653) 삭제 -> [-45]
4) I -642: -642 삽입 -> [-642, -45]
5) I 45: 45 삽입 -> [-642, -45, 45]
6) I 97: 97 삽입 -> [-642, -45, 45, 97]
7) D 1: 최댓값(97) 삭제 -> [-642, -45, 45]
8) D -1: 최솟값(-642) 삭제 -> [-45, 45]
9) I 333: 333 삽입 -> [-45, 45, 333]
10) [-45, 45, 333]에서 최댓값과 최솟값 return -> [333, -45]
"""

 

 

 

 

 

참고)

 

https://littlefoxdiary.tistory.com/3

[Python] 힙 자료구조 / 힙큐(heapq) / 파이썬에서 heapq 모듈 사용하기

 

https://velog.io/@norighthere/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-Python-%EC%9D%B4%EC%A4%91%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84%ED%81%90

[프로그래머스 / Python] 이중우선순위큐