[Python/Heap] 이중우선순위큐

문제

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

명령어	수신 탑(높이)
I 숫자	큐에 주어진 숫자를 삽입합니다.
D 1	큐에서 최댓값을 삭제합니다.
D -1	큐에서 최솟값을 삭제합니다.

이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

 

 

입출력 예

operations	return
["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"]	[0,0]
["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"]	[333, -45]

 

 

나의 풀이

def solution(operations):
    answer = []
    
    for oper in operations:
        if answer != []:
            if oper == 'D 1': #최대값 삭제
                answer.remove(max(answer))
            if oper == 'D -1': #최솟값 삭제
                answer.remove(min(answer))
            
        oper = oper.split(' ')
        if oper[0] == 'I':
            answer.append(int(oper[-1]))
            
    if answer == []:
        return [0,0]
    return answer

operations은 명령어를 담은 list, answer은 return할 heap - 헷갈리지 말 것

operations.remove(max(answer)) (X)

 

 

list에서 delete할 때 

1. del을 사용해 index로 삭제

>>> a = [1, 2, 3, 4, 5, 6, 7]
>>> del a[1]
>>> a
[1, 3, 4, 5, 6, 7]

2. remove를 사용해 item으로 삭제

>>> a = [1, 2, 3, 4, 5, 6, 7]
>>> a.remove(1)
>>> a

[2, 3, 4, 5, 6, 7]

 

 

python의 heapq 모듈을 사용한 풀이

파이썬의 heapq 모듈은 기본적으로 Min Heap 구조를 갖는다. 그렇기 때문에 heappop()을 하게되면 가장 heap에서 최솟값을 빼게 된다.

# heapq.nlargest(n, iterable, key=None)
# iterable에서 가장 큰 n개 추출

import heapq
nums = [1, 8, 3, -5, 4, 99, -4, 0]
print(heapq.nlargest(3, nums)) 
#[99, 8, 4]

heapq.heapify( x ) 
#목록 x 를 선형 시간에 제자리에 있는 힙으로 변환합니다.

 

 

mport heapq

def solution(operations):
    answer = []
    heap = []   # 힙 생성

    for data in operations:
        # 연산이 "I"일 경우 공백 뒤의 숫자를 heap에 넣음
        if data[0] == "I":
            heapq.heappush(heap, int(data[2:]))
        # 연산이 "D"일 경우
        else:
            if len(heap) == 0:
                pass
            # 공백 뒤가 "-"일 경우 최소힙을 제거
            elif data[2] == "-":
                heapq.heappop(heap)
            # 공백 뒤가 아무것도 아닌 경우
            else:
                # 힙에서 가장 큰 수를 제외하고 다시 힙에 넣음
                heap = heapq.nlargest(len(heap), heap)[1:]
                heapq.heapify(heap)

    if heap:
        answer.append(max(heap))
        answer.append(min(heap))
    else:
        answer.append(0)
        answer.append(0)
    
    return answer