[SWEA] [python] 5174, 5176, 5177, 5178 - Tree

문제링크: 문제해결 기본 Tree

SW Expert Academy

5174-Subtree D2

def node_num(root):
    global cnt 
    
    node = [root]
    while node:
        rt = node.pop()
        if left[rt]:
            node.append(left[rt]) 
            # should uncomment
            #cnt +=1 
        if right[rt]:
            node.append(right[rt])
            # should uncomment
            #cnt +=1

T = int(input())

for tc in range(T):
    E, N = map(int, input().split())
    arr = list(map(int, input().split()))

    cnt = 1

    # 루트에 자식 추가할 array 만들어주기
    left = [0]*(E+2) # 첫번째 자식
    right = [0]*(E+2) # 두번째 자식

    for i in range(0, len(arr), 2):
        parent, child = arr[i], arr[i+1]
        # 왼쪽 노드에 이미 값이 존재한다면 오른쪽 노드에 저장
        if left[parent]:
            right[parent] = child
        # 왼쪽 노드에 자식 노드가 없을 시 왼쪽 노드에 저장
        else:
            left[parent] = child
    
    node_num(N)
    print("#{} {}".format(tc + 1, cnt))

5176-이진탐색 D2

class Tree:
    def __init__(self, N):
        self.lst = [0] * (N + 1)
        self.N = N
        self.count = 1
        self.in_order(1)

    # 순서: left, root, right을 재귀적으로 탐색하며 숫자를 입력해준다. (in-order traversal)
    def in_order(self, num) :
        if num <= N:
            # 좌측 노드의 인덱스는 루트 노드의 두배
            # 좌측으로 계속 탐색해서 끝까지 내려감
            self.in_order(num *2)
            # root 노드 탐색
            self.lst[num] = self.count
            self.count += 1
            # 우측 노드의 인덱스는 루트 노드의 두배 + 1
            self.in_order(num * 2 + 1)
    

    def result(self):
        return ' '.join(map(str, (self.lst[1], self.lst[self.N // 2])))

T = int(input())
for tc in range(T):
    N = int(input())
    # 트리 생성, 넘버링 후 값 리턴까지
    tree = Tree(N)
    mid = tree.result
    print('#{} {}'.format(tc+1, tree.result()))

5177-이진힙 D2

class Tree:
    # initialize a list to append nodes
    def __init__(self):
        self.lst = [0]

   # sort nodes
    def sort(self, num):
        # while list has more than 2 elements
        if num >= 2:
            # if the parent node is larger than the child node
            if self.lst[num] < self.lst[num//2]:
                # swap places
                self.lst[num], self.lst[num//2] = self.lst[num//2], self.lst[num]
                # continue swapping
                self.sort(num//2)
    
    # append nodes to array and sort them
    def append(self, data):
        num = len(self.lst)
        self.lst.append(data)
        self.sort(num)

    def totalsum(self, node):
        if node <= 1 :
            return self.lst[node]
        else:
            return self.lst[node] + self.totalsum(node // 2)

    def result(self):
        last = len(self.lst) - 1
        # final result for the sum of parent node
        self.sum = 0
        # if there are parent nodes
        if last >= 2:
            return self.totalsum(last//2)
        else:
            return 0
        
T = int(input())

for tc in range(T):
    N = int(input())
    vals = list(map(int, input().split()))
    tree = Tree()
    for i in range(N):
        tree.append(vals[i])
    print("#{} {}".format(tc + 1, tree.result()))

    

5178 노드의 합 D3

def search(idx):
    idx = idx
    # add values to the parent node until it reaches the first node
    while idx > 1:
        node[idx//2] += node[idx]
        idx -=1


T = int(input())

for tc in range(T):
    N, M, L = map(int, input().split())
    node = [0] * (N + 1)
    for i in range(M):
        # add node values to each index
        idx, val = map(int, input().split())
        node[idx] = val
    
    # search from the last index
    search(N) 
    print("#{} {}".format(tc + 1, node[L]))