SWEA 5176 이진탐색

IngCoding·2022년 4월 12일

파이썬 #1 알고리즘

목록 보기

25/27

문제출처 SW Expert Academy
문제의 저작권은 SW Expert Academy에 있습니다.

문제소개

- 1부터 N까지의 자연수를 이진탐색트리에 저장하려고 한다. 
- 이진탐색트리의 루트 값과, N/2 노드(소수점 버림) 값을 출력하시오. 
- 트리의 값은 왼쪽 자식노드 < 현재 노드 < 오른쪽 자식노드 를 만족

1~6까지의 이진탐색트리 이미지)

입력:
1
6 

출력:
#1 4 6 (트리의 루트값 4, N/2(오른쪽 하단 루트 노드)값 6

풀이접근

- 리스트를 이용해 1~N 의 트리를 만듦
- 제일 왼쪽부터 규칙에 맞게 값을 넣어줌 (재귀함수 활용)

코드

# 입력된 tree에 종속되는 sub_tree의 함수 작성
def make_tree(n):
    global count
    
    # N값이 넘어가지 않아야함
    if n <= N:
        # 왼쪽노드는 현재 인덱스의 2배 
        # 예) 6인 경우 1 - 2 - 4 / 3 - 6
        make_tree(n*2)  # 함수 안에 함수(재귀함수) 활용 
        
        # 최하단 노드까지 갔으면 값 넣기
        tree[n] = count
        count += 1 # 다음값을 넣기 위해 count 증가
        
        # 오른쪽노드는 인덱스 2배 +1
        make_tree(n*2 + 1)
        
for tc in range(1, int(input()) + 1):
    N = int(input())
    
    # 트리표시를 위한 리스트 
    tree = [0 for i in range(N+1)]
    count = 1
    make_tree(1) # 함수에 가장 하단 왼쪽노드값인 1 대입 
        
    print(f'#{tc} {tree[1]} {tree[N//2]}')