프로그래머스 더 맵게 문제를 풀다가 리스트를 정렬하는 sort() 메소드를 사용하면 값은 나오는데 시간초과가 떠서,
배열을 heapq로 바꿔주는 heapify 대신 ( 제자리에서 힙으로 변환된다 )
원소 하나하나를 heappush 하면 힙의 불변성을 유지하며 push, pop 된다.
파이썬에 내장된 heapq는 이진 트리이며 최소힙을 사용한다고 한다.
1. 리스트를 그대로 힙으로 변환할 때
import heapq
arr = [9, 3, 2, 1, 12, 10]
heapq.heapify(arr)
print(arr) //[1, 3, 2, 9, 12, 10]
2. 원소 하나하나 heappush 할 때
import heapq
arr2 = [9, 3, 2, 1, 12, 10]
new_arr = []
for i in arr2:
heapq.heappush(new_arr, i)
print(new_arr) //[1, 2, 3, 9, 12, 10]
'알고리즘' 카테고리의 다른 글
[Python] bisect_left, bisect_right (0) | 2022.01.11 |
---|---|
[Python] 2019 KAKAO BLIND RECRUITMENT - 오픈채팅방 (0) | 2021.11.15 |
[Python] 프로그래머스 고득점 Kit (스택/큐) : 프린터 (0) | 2021.10.04 |
[Python] 프로그래머스 고득점 Kit (정렬) : K번째 수 (0) | 2021.10.04 |
[알고리즘] dx, dy 좌표 상하좌우 탐색 로직 (0) | 2021.09.27 |