SWEA 5177 이진 힙

문제출처 SW Expert Academy
문제의 저작권은 SW Expert Academy에 있습니다.

문제소개

- N개의 서로 다른 자연수가 주어지면 입력 순서대로 이진 최소힙에 추가함
- 힙은 최소 또는 최대값을 루트로 설정하여 빠르게 연산하도록 고안된 트리구조 
- 부모노드 < 자식노드 조건이 만족하도록 계속 부모 노드의 값을 바꿔줌
- 힙에 마지막 노드의 조상 노드에 저장된 정수의 합을 구하는 프로그램 작성 

입력:
1
6 (N개의 숫자 입력)
7 2 5 3 4 6 (입력 순서대로 최소힙에 저장)

출력:
#1 7 (마지막 노드인 6의 조상 노드값인 5와 2가 더해짐)  

풀이접근

- 리스트를 이용해 1~N 의 트리를 만듦
- 제일 왼쪽부터 규칙에 맞게 값을 넣어줌

코드

def min_heap(node):
    up_node = node//2
    if up_node < 0: # 루트노드에 도달하면 리턴
        return # return 안하면 maxdepth exceed 나옴
    else: 
        # 부모노드가 더 크면 위치 바꿔줌
        if tree[up_node] > tree[node]: 
            tree[node], tree[up_node] = tree[up_node], tree[node] 
            min_heap(up_node) # 함수에 부모노드 대입해서 반복 
            
for tc in range(1, int(input()) + 1):
    N = int(input()) # 노드갯수
    tree = [0] 
    node_num = 1 
    for num in map(int, input().split()):
        tree.append(num)
        min_heap(node_num)
        node_num += 1
    
    sum_value = 0
    while N: # N(마지막)노드의 조상노드 값들 더함
        N //= 2
        sum_value += tree[N]
    
    print(f'#{tc} {sum_value}')

 1
 6
 7 2 5 3 4 6


#1 7

정의된 변수 값 확인

tree

[0, 2, 3, 5, 7, 4, 6]

node_num

7