집 짓는 개발블로그
[프로그래머스] LV.3 이중우선순위큐 (Python) - heapq 본문
https://school.programmers.co.kr/learn/courses/30/lessons/42628
처음 제출한 코드
import heapq
def solution(operations):
heap = []
for operation in operations:
if operation.startswith("I"):
num = int(operation.split()[1])
heapq.heappush(heap, num)
elif operation == 'D 1':
if not heap:
continue
max_heap = []
min_heap = []
for element in heap:
heapq.heappush(max_heap, -element)
heapq.heappop(max_heap)
for element in max_heap:
heapq.heappush(min_heap, -element)
heap = min_heap
else:
if not heap:
continue
heapq.heappop(heap)
if not heap:
return [0, 0]
else:
return [max(heap), min(heap)]
max heap을 따로 만들어서 기존 최소 힙의 모든 원소를 -를 붙여 옮긴 뒤 heappop하는 방식이다. 더 좋은 방식이 있을까 싶어 찾아봤는데, 파이썬에서는 heapq모듈로 리스트를 힙처럼 사용하는 것이기 때문에 힙처럼 쓰고 있는 것도 사실은 '리스트'라는 사실을 알았다. 따라서 리스트 연산이 모두 사용 가능하다.
개선된 코드
def solution(operations):
heap = []
for operation in operations:
if operation.startswith("I"):
num = int(operation.split()[1])
heapq.heappush(heap, num)
elif operation == 'D 1':
if not heap:
continue
maxx:int = max(heap)
heap.remove(maxx)
else:
if not heap:
continue
heapq.heappop(heap)
if not heap:
return [0, 0]
else:
return [max(heap), min(heap)]
'알고리즘' 카테고리의 다른 글
[프로그래머스] LV.3 두 큐 합 같게 만들기 (Python) (0) | 2024.06.27 |
---|---|
[프로그래머스] LV.3 쿼드압축 후 개수 세기 (Python) (0) | 2024.06.27 |
[프로그래머스] LV.3 최고의 집합 (Python) (0) | 2024.06.23 |
(Python) 재귀함수 return에 대한 의문 풀이하기 (0) | 2024.06.23 |
[프로그래머스] LV.3 야근 지수 (Python) - heapq (0) | 2024.06.21 |