편집 시간: 2022년 2월 12일 오후 9:42
코드
Algorithm/1927.py at main · Junroot/Algorithm
풀이
python의 heapq를 이용하면 된다. 하지만 priority queue를 직접 구현해봤다.
새로운 값을 추가했을 때, 힙의 마지막에 추가한 뒤 자신위 부모보다 작을 때까지 하나씩 위로 올린다.
값을 삭제할 때는 가장 마지막 노드를 부모로 올린 뒤에 자신의 자식노드와 비교하면서 자신이 자식 노드보다 클 때 까지 아래로 하나씩 내린다. 이 때, 자식 둘이 모두 부모보다 작을 경우 둘 중 더 작은 자식과 교환해야된다.