Level 3 이중우선순위큐 Python3

https://programmers.co.kr/learn/courses/30/lessons/42628?language=python3 

코딩테스트 연습 - 이중우선순위큐

 

최종 코드

• GitHub https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_이중우선순위큐.py

hwayeon351/Programmers-Algorithms

from heapq import heappush, heappop
def solution(operations):
    answer = []
    heap = []
    for op in operations:
        if op[0] == "I":
            heappush(heap, int(op[2:]))
        elif heap:
            if op[2:] == "-1":
                heappop(heap)
            else:
                heap.remove(max(heap))
    if heap: return [max(heap), heap[0]]
    return [0, 0]

---

풀이 과정

풀이 시간 15분

1. deque 사용

from collections import deque
def solution(operations):
    q = deque()
    for op in operations:
        if op[0] == "I":
        	#큐에 숫자를 삽입할 때마다 오름차순 정렬
            q.append(int(op.split(" ")[1]))
            q = deque(sorted(q))
        else:
        	#큐에 아무것도 없는 경우 삭제할 수 없으므로 continue
            if len(q) == 0:
                continue
            #최솟값 삭제하는 경우 큐의 첫번째 요소 삭제
            elif op[2:] == "-1":
                q.popleft()
            #최댓값 삭제하는 경우 큐의 마지막 요소 삭제
            else:
                q.pop()
    #큐에 아무것도 없는 경우 return [0,0]
    if len(q) == 0: return [0,0]
    #큐에 숫자가 있는 경우 return [최댓값,최솟값]
    return [q[-1], q[0]]
#시간복잡도 = O(n^2 log n), 공간복잡도 = O(n)

 

2. heapq 사용

from heapq import heappush, heappop
def solution(operations):
    answer = []
    heap = []
    for op in operations:
    	#힙에 숫자를 삽입하는 경우
        if op[0] == "I":
            heappush(heap, int(op[2:]))
        #힙이 비어있지 않을 때 숫자를 삭제하는 경우
        elif heap:
        	#최솟값을 삭제하는 경우, 힙의 root를 삭제
            if op[2:] == "-1":
                heappop(heap)
            #최댓값을 삭제하는 경우, 리스트 heap의 max값을 remove
            else:
                heap.remove(max(heap))
    #heap이 비어있지 않은 경우, return [최댓값, 최솟값]
    if heap: return [max(heap), heap[0]]
    #heap이 비어있는 경우, return [0,0]
    return [0, 0]