프로그래머스 3단계 "이중우선순위 큐"

문제

프로그래머스 '이중우선순위 큐'

풀이

문제를 일반적인 리스트의 max 및 min을 사용해도 문제없이 풀수 있지만 문제 분류가 힙으로 되어있는 만큼 힙을 이용하여 문제를 풀었다.

파이썬의 heapq가 기본적으로 최소힙으로 이루어져 있어 최대값을 pop해주는데 있어 손을 좀 써야했다.

최소힙과 최대힙 두개를 만들어 동시에 조작하는 방법도 있지만 나는 heapq.nlargest를 이용하여 최대값을 찾고, 그 인덱스를 구해 pop하는 형식으로 코드를 구현하였다.

heapq.nlargest(a, b)는 원하는 수(a)와 힙(b)을 인수로 받아 힙에서 가장 큰 수 a개를 리스트로 반환하는 함수이다.

반대로 heapq.nsmallest(a, b)는 가장 작은 수를 a개 찾는 함수이다.

자세한건 여기를 참조하자.

Python 코드

import heapq

def solution(operations):
  que = []

  for x in operations:
    oper, num = x.split()
    num = int(num)

    # 인덱스 오류날 시를 대비한 예외 처리
    try:
      if x == 'D 1':
        # heapq의 nlargest를 이용하여 최대값을 구하고, 해당 인덱스 pop
        print(heapq.nlargest(1, que)[0])
        que.pop(que.index(heapq.nlargest(1, que)[0]))
      elif x == 'D -1':
        # heappop을 이용해 최소값 pop
        heapq.heappop(que)
      else:
        # I일 경우 이중순위큐에 push
        heapq.heappush(que, num)
    except IndexError:
      pass

  if not que:
    return [0, 0]
  else:
    return [max(que), min(que)]