[알고리즘] 프로그래머스 - 이중우선순위큐

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

다른 사람 풀이 1

import heapq

def solution(operations):
  heap = []
  for operation in operations:
      cmd, num = operation.split()
      if cmd == "I":
          heapq.heappush(heap, int(num))
      else:
          if heap:
              if num == "1":
                  heap.pop(heap.index(heapq.nlargest(1, heap)[0]))
              else: # 최솟값 삭제
                  heapq.heappop(heap)

  if not heap:
      return [0,0]
  return [heapq.nlargest(1, heap)[0], heapq.nsmallest(1, heap)[0]]

파이썬의 heapq에는 내장 함수로 nlargest와 nsmallest를 지원한다는 것을 알게 되었다. nlargest(개수, heap)의 리턴에는 여러 개가 될 수도 있으므로 한 개일지라도 리스트로 반환한다. 따라서 heapq.nlargest(1, heap)[0]가 된다.

다른 사람 풀이 2

import heapq

def solution(operations):
    heap = []
    for operation in operations:
        cmd, num = operation.split()
        if cmd == "I":
            heapq.heappush(heap, int(num))
        else:
            if heap:
                if num == "1": #최대값 삭제
                    heap.remove(max(heap))
                else: # 최솟값 삭제
                    heapq.heappop(heap)

    if not heap:
        return [0,0]
    return [max(heap), heap[0]]

파이썬은 스택, 큐, 힙 모두 리스트를 기반으로 구현되었다는 것을 이용하여 그냥 최대값을 제거할때에는 리스트에서 remove를 사용해도 된다. 다른 풀이를 보니 심지어 그냥 리스트를 이용하고 매번 정렬을 해주는 것도 통과한다.