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

 

 

📌 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42628

프로그래머스

 

 

최대, 최소 문제의 경우에는 heap을 사용하는 것이 일반적이다. 왜냐하면 시간복잡도가 굉장히 낮은 자료구조이기 때문이다.

 

👩‍💻 전체코드

from heapq import heappush, heappop

def solution(operations):
    answer = []
    heap = []
    for i in operations:
        if i.split()[0] == 'I' :
            heappush(heap, int(i.split()[1]))
        elif i.split()[0] == 'D':
            if len(heap) > 0:
                if i.split()[1] == '-1':
                    heappop(heap)
                elif i.split()[1] == '1':
                    heap.pop(-1)
                    
    if len(heap) == 0:
        answer = [0,0]
    else:
        answer.append(max(heap))
        answer.append(min(heap))
    return answer

 

 

1. heap을 사용하기 위해 heapq를 import 해준다.

 

2. 각각의 operations들을 split해서 공백을 기준으로 나누어본다

- I 인 경우 : heappush 적용

- D 인 경우 : heap에 원소가 없으면 pop을 할 수 없으므로 길이 확인 & -1인 경우에는 최솟값을 삭제하므로 heappop사용, 1인 경우에는 가장 뒤에 있는(가장 큰) 원소 pop

 

3. 최종 출력

- 길이가 0인 경우에는 [0,0] 출력

- 길이가 0 이상인 경우에는 heap에서 최대값, 최소값 append하여 출력