[프로그래머스] 힙(heap) - 이중우선순위큐 (Python)

문제출처 : 프로그래머스

👻 문제

• 문제 설명
  이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.
  이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.
  

---

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

---

• 입출력 예
  

---

• 입출력 예 설명

  입출력 예 #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]를 반환합니다.

---

🛠️ 새로 배운 함수

• nlargest()와 nsmallest() 함수를 사용해 최대 또는 최소값을 찾을 수 있다.

heapq.nlargest(n, iterable, key=None)
heapq.nsmallest(n, iterable, key=None)

---

• 함수를 사용하면 list에서 가장 큰 n개의 수를 뽑아낼 수 있다. 하기 코드에서는 heap의 전체 원소 개수만큼 뽑고, 전체 heap 리스트가 내림차순으로 정렬된다. 그 후 인덱스 1부터 슬라이싱하면 가장 큰 최대값이 제외된다.

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

---

👩‍💻 My cording

풀이 : heapq 모듈, for문, if문 활용

import heapq as hq

def solution(operations):
  answer=[]
  heap=[]
   
  for op in operations:
    # 첫글자가 "I"일 때, 세번째부터 [heap]에 추가
    if op[0] == "I":
      hq.heappush(heap, int(op[2:]))
    else:
      if len(heap) == 0: # heap 요소의 개수가 =0이면, pass
        pass
      # 세번째가 "-"이면 최솟값 삭제
        # heappop : 가장 작은 원소를 삭제 후에 그 값을 리턴
      elif op[2] == "-":
        hq.heappop(heap)
      else:
        #nlargest()와 nsmallest() 함수를 사용해 최대 or 최소값을 찾을 수 있음
        #nlargest(n, iterable, key=None) 
        heap = hq.nlargest(len(heap), heap)[1:]
        # 누군가 최댓값을 내놓으라 한다면
        # 주저없이 최상단레벨의 root 노드인 10을 내어주면 된다.
        # 10이 나가고 나면 트리가 깨진다.
        # 이때 나중에 또 최댓값을 내놓으라 할 수 있으니, 다시 힙 형태로 바꿔놓자. heapify()
        hq.heapify(heap)
 
  if heap:
    answer.append(max(heap))
    answer.append(min(heap))

  else:
    answer.append(0)
    answer.append(0)

  return answer

---

💡check point

• heapq.nlargest() 부가설명

 import heapq as hq
heap = [8, 3, 4, 1, 7, 10]
heap = hq.nlargest(len(heap), heap)[2:]
print(heap)

---

• 예시
  1) heap = hq.nlargest(len(heap), heap)
  → 출력값 : 내림차순 정렬 [10, 8, 7, 4, 3, 1]
  2) heap = hq.nlargest(len(heap), heap)[0:]
  → 출력값 : [10, 8, 7, 4, 3, 1]
  3) heap = hq.nlargest(len(heap), heap)[1:]
  → 출력값 : 맨 앞 숫자 슬라이싱 후, [8, 7, 4, 3, 1]
  4) heap = hq.nlargest(len(heap), heap)[2:]
  → 출력값 : 맨 앞 숫자 2개 슬라이싱 후, [7, 4, 3, 1]

---

💭 반성할 점

처음 heapppush()를 할 때, int()로 정수 변환해서 push해주지 않았더니 계속 오류가 났었다. 왜 오류가 났는지 한참 찾았는데, 완전 어이없고 사소한 실수였다, 실수하지 말자!

hq.heappush(heap, 💡int(i[2:]))