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

# 문제 설명

이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말한다.

명령어	기능
I 숫자	큐에 주어진 숫자를 삽입
D 1	큐에서 최대값 삭제
D -1	큐에서 최소값 삭제

이중 우선순위 큐가 연산할 명령들이 주어질 때, 모든 연산을 처리한 후 [최대값, 최소값]을 반환해라.

최대값, 최소값을 삭제하는 연산에서 해당하는 값이 2개 이상인 경우, 하나만 삭제한다.

빈 큐에 데이터를 삭제하는 연산이 주어질 경우, 해당 연산은 무시한다.

단, 처리한 후 큐가 비어있다면 -1을 반환한다.

 

# 입출력 예시

입력	출력
["I 16", "D 1"]	[0, 0]
["I 7", "I 5", "I -5", "D -1"]	[7, 5]

 

# 코드 풀이

from heapq import heappush, heappop, nlargest, nsmallest
def solution(operations):
    answer = []
    q = []
    for row in operations:
        op, x = row.split(' ')
        if op == 'I':
            heappush(q, int(x))
        elif not q: # D 연산인데 empty q라면
            continue
        elif x == '-1':
            heappop(q)
        else:
            q.pop()
    if not q:
        return [0, 0]
    return [*nlargest(1, q), *nsmallest(1, q)]

 

# 핵심 포인트

• q에서 가장 큰 n개의 값을 반환하기 위해 heapq.nlargest(n, q)를, 가장 작은 값을 위해서는 heapq.nsmallest(n, q)를 사용한다.