[프로그래머스] Lv3. 이중우선순위큐

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42628

프로그래머스

코드

import heapq
def solution(operations):
    com,num = [],[]
    q = []
    for i in operations:
        a,b= i.split(" ")
        if a == 'I':
            q.append(int(b))
            q.sort()
        else:
            if not q:
                continue
            else:
                if b == '-1':
                    heapq.heappop(q)
                else:
                    q= heapq.nlargest(len(q),q)[1:]
                    heapq.heapify(q)
    if q:
        return [max(q),min(q)]
    else:
        return [0,0]

풀이

• 처음에 이 문제를 접근할때 최소 힙, 최대 힙을 각각 따로 만들어서 한 힙에서 값을 빼면, 동시에 다른 힙에서 그 값을 pop하는 식으로 구성했으나, 시간복잡도가 커지고, 코드가 지저분해서 다른 방법을 생각했다.
• 구글링을 하다보니 힙큐에도 내림차,오름차로 정렬해서 리스트를 반환하는 함수가 있다는 것을 찾았다.
  • heapq.nlargiest(n,iterable,key=None): iterable 객체에서 n개만큼 오름차순으로 정렬한 리스트를 반환한다.
  • heapq.nsmallest(n,iterable,key=None): iterable 객체에서 n개만큼 내림차순으로 정렬한 리스트를 반환한다.

이를 이용해서 len(q)만큼 정렬시키면 q 전체를 오름차순으로 정렬된 리스트를 받을 수 있고, 가장 큰 값이 0번이므로 q에 0번 인덱스를 제외한 리스트를 넣어주고, heapq.heapify(q)로 다시 최소 힙으로 만들면 해결되었다.