[swea] 5177. 이진힙 / python 파이썬

🚩 트리(tree)

 

thinking

[부모노드, 왼쪽자식, 오른쪽자식, 노드값] 의 2차원 리스트 형태의 트리를 만들고 input data 값을 넣어준다.

왼쪽자식, 오른쪽자식의 노드번호가 1씩 차이나므로 인덱스를 홀짝으로 접근해 값을 넣어줬고,

만약 전체 노드의 개수가 짝수인 경우 오른쪽 자식이 없으므로 0으로 다시 할당해주는 조건문을 설정했다.

change 라는 함수를 통해 부모<자식이 되도록 바꿔주는데, 재귀적으로 접근하지 않을 경우

만약 5-3-1의 경우라면 함수 1번 시행시에 3-5-1, 함수 2번 시행시에 3-1-5가 되어

전체적으로 봤을 때 부모<자식이 항상 성립하지 않게 된다.

(처음 코드를 작성했을 때 재귀로 구성하지 않아 9개의 testcase 중 3개만 맞았다.)

재귀로 부모<자식이 될때까지 계속해서 돌려야하는데, 자식노드를 기준으로 부모노드를 비교하도록 했다.

 

코드

T = int(input())

def change(node):
    parent = tree[node][0]
    if parent:
        if tree[parent][3] > tree[node][3]:
            tree[parent][3], tree[node][3] = tree[node][3], tree[parent][3]
    else:
        return
    change(parent)


def sum_root(N):
    global ans
    if tree[N][0] == 0:
        return
    ans += tree[tree[N][0]][3]
    sum_root(tree[N][0])


for tc in range(1, T+1):
    N = int(input())
    tmp = list(map(int, input().split()))
    tree = [[0]*4 for _ in range(N+1)]  # [부모노드,왼쪽자식,오른쪽자식,노드값]

    for i in range(1, N+1):
        tree[i][3] = tmp[i-1]
        tree[i][0] = i // 2
        if 2 * i <= N:
            tree[i][1] = 2 * i
            tree[i][2] = 2 * i + 1
            if 2*i+1 > N:
                tree[i][2] = 0

    for i in range(1, N+1):
        change(i)

    ans = 0
    sum_root(N)

    print("#{} {}".format(tc, ans))