[알고리즘] 백준 5639 '이진 검색 트리' 풀이 _ 파이썬
백준 5639 이진 검색 트리
https://www.acmicpc.net/problem/5639
난이도 : 실버 1
유형 : 트리
문제
이진 검색 트리를 전위 순회한 순서대로 노드가 주어졌을 때, 이 트리를 후위 순회한 순서대로 노드를 출력하는 문제.
풀이
기본적으로 이진 트리 문제였기 때문에 재귀를 사용해서 풀려고 했다.
함수를 만들어서 배열을 넘겨가면서 제일 앞에 있는 수를 루트 노드, 뒤의 배열 중 루트 보다 작은 숫자까지를 왼쪽 배열,나머지를 오른쪽 배열로 3부분으로 나눠주었다.
나눈 부분을 후위 순회하기 위해서 왼쪽 배열을 먼저 재귀로 넘기고, 그 다음 오른쪽 배열을 재귀로 넘기고, 마지막으로 루트 노드 값을 출력했다.
정답 코드
import sys
input = sys.stdin.readline
#recursion error 방지
sys.setrecursionlimit(10**9)
arr = []
while True:
try:
x = int(input())
arr.append(x)
except:
break
def solution(A):
# 받은 배열 길이가 0이면 return
if len(A) == 0:
return
tempL, tempR = [], []
# 첫번째 값을 루트 노드로 설정
mid = A[0]
# 나머지 배열에 대해 for문을 돌면서 루트보다 커지는 부분을 기록해서 L과 R로 나눈다.
for i in range(1, len(A)):
if A[i] > mid:
tempL = A[1:i]
tempR = A[i:]
break
else:
#모두 mid보다 작은 경우
tempL = A[1:]
#왼쪽, 오른쪽 순으로 재귀 후 루트 노드 값 출력
solution(tempL)
solution(tempR)
print(mid)
solution(arr)
Author And Source
이 문제에 관하여([알고리즘] 백준 5639 '이진 검색 트리' 풀이 _ 파이썬), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@nkrang/알고리즘-백준-5639-이진-탐색-트리-풀이-파이썬저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)