[파이썬] 5178. 노드의 합

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.


완전 이진 트리의 리프 노드에 1000이하의 자연수가 저장되어 있고, 리프 노드를 제외한 노드에는 자식 노드에 저장된 값의 합이 들어있다고 한다.

다음은 리프 노드에 저장된 1, 2, 3이 주어졌을 때, 나머지 노드에 자식 노드의 합을 저장한 예이다.
  

N개의 노드를 갖는 완전 이진 트리의 노드 번호는 루트가 1번이 되며, 같은 단계에서는 왼쪽에서 오른쪽으로 증가, 단계가 꽉 차면 다음단계의 왼쪽부터 시작된다.

완전 이진 트리의 특성상 1번부터 N번까지 빠지는 노드 번호는 없다.

리프 노드의 번호와 저장된 값이 주어지면 나머지 노드에 자식 노드 값의 합을 저장한 다음, 지정한 노드 번호에 저장된 값을 출력하는 프로그램을 작성 하시오.


[입력]

첫 줄에 테스트케이스의 수 T가 주어진다. 1<=T<=50

다음 줄부터 테스트 케이스의 별로 노드의 개수 N과 리프 노드의 개수 M, 값을 출력할 노드 번호 L이 주어지고, 다음 줄부터 M개의 줄에 걸쳐 리프 노드 번호와 1000이하의 자연수가 주어진다.

[출력]

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

입력	출력
3 5 3 2 4 1 5 2 3 3 10 5 2 8 42 9 468 10 335 6 501 7 170 17 9 4 16 479 17 359 9 963 10 465 11 706 12 146 13 282 14 828 15 962	#1 3 #2 845 #3 1801

 

🎀 나의 풀이

 

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    N, M, L = map(int, input().split())		# 노드의 개수, 리프 노드의 개수, 출력할 노드 번호
    lst=[0]*(N+1)					# 노드의 개수+1만큼 트리 생성
    for _ in range(M) :					# 트리에 리프 노드 데이터 삽입
        idx, data = map(int, input().split())		# 리프 노드 번호, 수
        lst[idx]=data
    for i in range(N-M, 0, -1) :	
        try:
            lst[i]=lst[i*2]+lst[i*2+1]		# 리프 노드를 제외한 노드=자식 노드에 저장된 값의 합
        except :
            lst[i]=lst[i*2]			# 오른쪽 자식이 없을 경우
    
    print(f"#{test_case} {lst[L]}")

 

1번부터 N번까지 노드를 가지는 트리를 만들기 위해 노드의 개수N+1만큼 리스트를 생성.

M개의 리프 노드를 입력받고 lst에 저장.

리프 노드를 제외한 노드의 개수를 역순으로 반복한다. 

왼쪽 자식은 i*2, 오른쪽 자식은 i*2+1이다.

테스트 케이스 2의 경우 5번 노드는 왼쪽 자식만 가지고 있다. 이처럼 오른쪽 자식이 없을 경우 왼쪽 자식의 값만 넣는다.

 

🎁 다른사람 풀이

 

T=int(input())
for tc in range(T) :
  # 인풋
  N, M, K = list(map(int, input().split()))

  # 완전이진트리
  q=[0 for i in range(N+1)]

  for _ in range(M):
    # 인풋을 받고 해당 위치에 넣어줌
    nodeid, nodeitem = list(map(int, input().split()))
    q[nodeid]=nodeitem

  # 뒤에서부터 오면서 합을 구하기
  # 끝 수가 짝수인 경우(=이진트리 마지막에 형제노드가 없는 경우)는 해당 부모 노드에 그냥 그 값을 넣는다.
  if N % 2 == 0 :
    q[N//2]=q[N]
    N-=1
  
  while N > 1 :   # 1인 경우는 부모 노드가 없다.
    q[N//2]=q[N]+q[N-1]
    N-=2    # 노드 두 개의 합을 계산했으니 두 칸씩 이동

  # K번째 노드에 들어있는 값 출력
  print("#%d %d" %(tc+1, q[K]))

 

마지막 노드 번호가 짝수면 자식 노드가 1개이기 때문에 왼쪽 자식 노드 값을 넣는다.

루트를 제외하고 부모 노드에 자식 노드의 합을 넣는다.

 

def dfs(idx):
  # 만약 인덱스 범위를 벗어난다면 0 리턴
  if idx > N +1 : return 0
  # 값이 있다면 값 리턴
  if Tree[idx]: return Tree[idx]
  # 왼쪽 자식노드 위치 찾기
  left=idx*2
  # 오른쪽 자식노드 위치 찾기
  right=left+1
  # 재귀를 이용해 구하기
  Tree[idx]=dfs(left)+dfs(right)
  # 결과값 리턴
  return Tree[idx]

for t in range(int(input())):
  # 별도 노드개수, 리프노드의 개수, 출력노드 번호
  N, M, L = map(int, input().split())
  # 누적합을 적어둔 리스트
  Tree=[0 for _ in range(N+2)]
  # 입력값을 받아 노드의 값을 수정
  for i in range(M):
    node, value=map(int, input().split())
    Tree[node]=value
  # 재귀를 이용해 계산 시작
  result=dfs(L)
  # 결과값 출력
  print('#{} {}'.format(t+1, result))

 

재귀를 이용한 풀이.

인덱스 범위가 N+1을 벗어나면 0을 리턴하고 해당 인덱스에 값이 있으면 그 값을 반환.

 

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

  def put(self, num1, num2):    # leaf 입력
    self.lst[num1]=num2

  def search_leaf(self, node):
    if node*2>N:    # leaf
      self.sum+=self.lst[node]  # 누적 합
    else:   # branch
      self.search_leaf(node*2)  # left 탐색
      if node*2 != N :    # right 존재하면
        self.search_leaf(node*2+1)    # right 탐색

  # 노드L의 자식들 중 leaf만 찾아 누적 합 리턴
  def my_result(self, L):
    self.sum=0
    self.search_leaf(L)
    return self.sum

T=int(input())
for test_case in range(1, T+1):
  N, M, L = map(int, input().split())
  tree=Tree(N)
  for _ in range(M) :
    num1, num2=map(int, input().split())
    tree.put(num1, num2)
  print('#{} {}'.format(test_case, tree.my_result(L)))

 

노드를 다 구하지 않고 출력할 노드 번호의 값만 구한다(효율적이다).

노드 번호 L의 마지막 레벨에 있는 자식 노드까지 내려간 후 거꾸로 올라오며 누적해서 더한다. 

node*2가 노드 개수N과 같지 않다는 것은 오른쪽에 값이 더 있다는 뜻.