[Python] SWEA 5178 노드의 합

SW Expert Academy SWEA 5178 노드의 합 문제는 완전 이진트리의 리프 노드에 수가 저장되어 있고, 나머지 노드에는 자식 노드 값의 합이 들어갈 때 특정 노드 번호의 값을 출력하는 문제이다. binary tree 이진트리 자료구조에 관한 문제로 난이도는 D3다.

 

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

 

SW Expert Academy 5178 노드의 합 문제 정보

자료구조 분류

- tree 트리, binary tree 이진트리, 완전 이진트리

난이도

- D3

 

노드의 합 문제 요약

• 완전 이진트리의 리프 노드에 1000 이하의 자연수가 저장되어 있다.
• 리프 노드를 제외한 노드에는 자식 노드에 저장된 값의 합이 들어있다.
• N개의 노드를 갖는 완전 이진트리의 노드 번호는 루트가 1번이 되며, 같은 단계에서는 왼쪽에서 오른쪽으로 증가, 단계가 꽉 차면 다음 단계의 왼쪽부터 시작된다.
• 완전 이진트리의 특성상 1번부터 N번까지 빠지는 노드 번호는 없다.
• 리프 노드의 번호와 저장된 값이 주어지면 나머지 노드에 자식 노드 값의 합을 저장한 다음, 지정한 노드 번호에 저장된 값을 출력한다.

 

문제 풀이 과정

1. 노드의 개수만큼 완전 이진트리를 구현하고, 리프 노드에 입력받은 값을 저장한다.
2. 트리의 맨 뒤부터 노드를 탐색하며 부모 노드에 자식 노드의 값을 더한다.
3. 테스트 케이스 번호, 지정한 노드 번호에 저장된 값을 출력한다.

 

코드 및 설명

for tc in range(int(input())):
    N, M, L = map(int, input().split())

    tree = [0 for _ in range(N + 1)]

    for _ in range(M):
        idx, value = map(int, input().split())
        tree[idx] = value

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

    print("#{} {}".format(tc + 1, tree[L]))

---

 

SW Expert Academy SWEA 5178 노드의 합 문제는 binary tree 이진트리, 완전 이진트리 자료구조 활용 문제이며 파이썬으로 구현하였다. 난이도는 D3이다.