SWEA 5177 - 이진 힙

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVJ-_6qfsDFAWg&&#

 

처음 든 생각

- 노드의 개수+1 개 만큼 담을 수 있는 힙을 불러와주고

- 하나씩 append하면서 부모 노드와 비교하면서 필요한 경우 스왑을 해줘야겠다.

 

나의 답

T = int(input())
from collections import deque
for test_case in range(1, T + 1):
    N = int(input())
    num_list = deque(list(map(int, input().split())))
    min_heap = [0]
    def check_parent(i):
        global min_heap
        if min_heap[i//2] > min_heap[i]:
            min_heap[i//2], min_heap[i] = min_heap[i], min_heap[i//2]
            check_parent(i//2)
    for i in range(1,N+1):
        min_heap.append(num_list.popleft())
        check_parent(i)
    result = -min_heap[len(min_heap)-1]
    while N >=1:
        result += min_heap[N]
        N = N // 2
    print(f"#{test_case} {result}")

 

받아온 숫자들을 왼쪽부터 하나씩 pop을 하기 위해서 큐를 사용했다.

 

작은 숫자가 가장 위에 오는 힙이기에 min_heap 으로 선언을 하였고 하나씩 popleft해주면서 append를 한다.

그리고 그 노드의 값과 부모 노드의 값을 비교해준다.

 

check_parent의 경우 부모노드와 비교해서 본인이 작으면 스왑을 하고 다시 부모노드와 비교할 수 있도록 재귀적으로 호출하였다.

 

그렇게 최소 힙을 완성한 다음 결과 처리만 해주면 끝이다. 

 

힙 문제를 풀 때 1번 노드, 2번 노드 이런식으로 하기 때문에 맨 처음은 0으로 사용하지 않는 노드로 간주하고 항상 인덱스와 노드 번호가 일치하게 처리될 수 있도록 선언해야한다.