SWEA 5176バイナリナビゲーション
6359 ワード
問題のソースソフトウェアExpert Academy
問題の著作権は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]}')
1
6
#1 4 6
定義された変数値の決定
tree
[0, 4, 2, 6, 1, 3, 5]
count
7
Reference
この問題について(SWEA 5176バイナリナビゲーション), 我々は、より多くの情報をここで見つけました https://velog.io/@wltn39/SWEA-5176-이진탐색テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol