[Python] 5178. 노드의 합

처음 코드

tc = int(input())
for idx in range(1, tc+1):
    n, m, l = map(int, input().split())  # 노드의 개수 n, 리프 노드의 개수 m, 값을 출력할 노드 번호 l
    node = [0 for _ in range(n+1)]

    for _ in range(m):
        leaf, num = map(int, input().split())
        node[leaf] = num

    if n % 2: # 노드의 개수가 홀수인경우 아래에서 자식노드 i, i+1을 더해서 부모노드에 넣어주니까
        n -= 1  # -1을 해줄 필요가 있다. (즉, i+1때문에)

    for i in range(n, 1, -2):
        try:    # 자식 노드 두개 더해서 부모 노드에 넣어준다.
            node[i//2] = node[i] + node[i + 1]
        except IndexError:
            node[i//2] = node[i]    # 노드 개수 짝수인 경우는 하나 남기 때문에 예외처리.

        if node[l]: # 출력할 노드 번호의 값을 찾았다면 멈춰
            break

    print('#{} {}'.format(idx, node[l]))

 

두번째 코드

팀원의 도움을 받아 더 간단해졌다.
노드의 개수가 홀수인지 짝수인지 구분할 필요 없고, try except문을 쓸 필요 없이
node 리스트를 넉넉하게 만들었다. 

tc = int(input())
for idx in range(1, tc+1):
    n, m, l = map(int, input().split())  # 노드의 개수 n, 리프 노드의 개수 m, 값을 출력할 노드 번호 l
    node = [0 for _ in range(n+2)]  # n이 짝수인 경우, 노드 개수가 하나 남기 때문에 아래에서 인덱스 에러를 막기 위해 넉넉하게 하나 더 만들어줌

    # 리프 노드 데이터 삽입
    for _ in range(m):
        leaf, num = map(int, input().split())
        node[leaf] = num

    # 값이 비어있는 노드부터 거꾸로 올라감
    for i in range(n-m, 0, -1):
        node[i] = node[i*2] + node[i*2+1]   # 부모노드 i에 자식노드 두개 더해 넣어주기

    print('#{} {}'.format(idx, node[l]))

 

다른 팀원의 코드

1. 재귀로 해결

def recur(cur):
    if cur > N: # 인덱스 초과하면 0리턴해야 0더함
        return 0

    if node[cur]: # 값 있으면 그거 리턴해,기저 조건
        return node[cur]

    return recur(cur * 2) + recur(cur * 2 + 1)

tc = int(input())
for k in range(1, tc + 1):
    N, M, L = map(int, input().split()) # 노드개수, 리프노드개수, 출력할노드
    leaf = [list(map(int, input().split())) for i in range(M)] # 리프노드 번호, 자연수

    node = [0 for i in range(N + 1)]
    for i in range(M):
        node[leaf[i][0]] = leaf[i][1]

    print('#{} {}'.format(k, recur(L)))

 

2. 후위 순회로 해결

def post_order(n):
    if n <= N and not node[n]:
        post_order(2*n)
        post_order(2*n+1)
        node[n] = node[2*n] + node[2*n+1]


for tc in range(int(input())):
    N, M, L = map(int, input().split())     # N: 노드 개수, M: 리프 노드 개수, L: 출력할 노드 번호
    node = [0] * (N+2)                      # 마지막 노드의 형제가 없는 경우 index error를 피하기 위해

    # 리프 노드 채우기
    for _ in range(M):
        n, v = map(int, input().split())
        node[n] = v

    # node 채우기 (후위 순회)
    post_order(1)

    print('#{} {}'.format(tc+1, node[L]))