문제
풀이 과정
1) 문제 이해 및 접근
문제에서 '완전 이진 트리' 및 주어진 조건, 노드의 총 개수 등을 확인하였을때, '포화 이진 트리' 라고 판단하였습니다.
트리의 중위 순회의 특징인 왼쪽 "자식 노드 / 부모 노드 / 오른쪽 자식 노드" 고려하여 재귀를 이용하는 풀이 방법을 생각했습니다.
2) 알고리즘
- 트리 순회 (중위 순회, In_order)
- 재귀
3) 풀이 코드
사용 언어 - Python
import sys
sys.stdin = open('input.txt')
# 중위 순회를 하며 각 노드를 층별로 배치 시키는 함수
def solution(left, root, right, depth): # 왼쪽 자식 노드 시작 인덱스 / 부모 노드 인덱스
# 오른쪽 자식 노드 끝 인덱스 / 트리의 레벨
if left >= root: # 리프 노드일때
level[depth].append(in_order_li[root]) # 현재 노드의 레벨에 노드 번호 추가
return
solution(left, (left+root)//2, root-1, depth+1) # 왼쪽 자식 노드 재귀 호출
level[depth].append(in_order_li[root]) # 부모 노드 해당하는 층에 노드 번호 추가
solution(root+1, (root+right+1)//2, right, depth+1) # 오른쪽 자식 노드 재귀 호출
K = int(sys.stdin.readline()) # 트리의 레벨(깊이)
in_order_li = list(map(int, sys.stdin.readline().split())) # 문제에서 주어진 중위순회 한 결과값
level = [[] for _ in range(K)] # 트리의 각 레벨별 노드 리스트
solution(0, (2**K-1)//2, 2**K-1, 0) # 트리 중위 순회시키는 함수 호출
for i in range(K): # 출력
print(*level[i])
결과 및 학습한 내용
1) 어려웠던 내용
재귀 호출을 하는 과정에서 노드들의 인덱스를 컨트롤 하는 부분에 주의를 기울였습니다.
문제 링크
https://www.acmicpc.net/problem/9934
※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다
'알고리즘 문제풀이 > Python' 카테고리의 다른 글
[백준] 2357 최솟값과 최댓값 (0) | 2021.12.21 |
---|---|
[프로그래머스] 트리 트리오 중간값 (0) | 2021.12.20 |
[백준] 2042 구간 합 구하기 (0) | 2021.12.19 |
[백준] 1167 트리의 지름 (0) | 2021.12.18 |
[백준] 1535 안녕 (0) | 2021.12.16 |
댓글