문제
1부터 N까지의 자연수를 이진 탐색 트리에 저장하려고 한다.
이진 탐색 트리는 어떤 경우에도 저장된 값이 왼쪽 서브트리의 루트 <현재 노드 <오른쪽 서브 트리의 루트인 규칙을 만족한다.
추가나 삭제가 없는 경우에는, 완전 이진 트리가 되도록 만들면 효율적인 이진 탐색 트리를 만들수 있다.
다음은 1부터 6까지의 숫자를 완전 이진 트리 형태인 이진 탐색 트리에 저장한 경우이다.
완전 이진 트리의 노드 번호는 루트를 1번으로 하고 아래로 내려가면서 왼쪽에서 오른쪽 순으로 증가한다.
N이 주어졌을 때 완전 이진 트리로 만든 이진 탐색 트리의 루트에 저장된 값과, N/2번 노드(N이 홀수인 경우 소수점 버림)에 저장된 값을 출력하는 프로그램을 만드시오.
[입력]
첫 줄에 테스트케이스의 수 T가 주어진다. 1<=T<=50
다음 줄부터 테스트 케이스의 별로 N이 주어진다. 1<=N<=1000
[출력]
각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.
풀이
잘 해결되지 않아 찾아보았다.
maketree라는 함수를 만들어준다. 함수의 목적은 tree리스트에 값을 할당하기 위함이고, 인덱스 1부터 시작해 N까지 커진다.
완전 이진트리의 노드별 인덱스 중 부모노드가 i이면 자식노드는 2i, 2i+1이라는 특성을 이용한다. maketree함수 안에서 왼쪽자식,오른쪽자식노드는 maketree함수를 재귀호출을 해주고, tree리스트에 cnt값을 넣어준다.
코드
def maketree(num):
global cnt
if num <= N:
maketree(2*num) #왼쪽노드
tree[num] = cnt
cnt +=1
maketree(2*num+1) #오른쪽노드
T = int(input())
for test_case in range(1, T+1):
N = int(input())
tree = [0 for _ in range(N+1)]
cnt = 1
maketree(1)
print(f'#{test_case} {tree[1]} {tree[N//2]}')
SW Engineer