[BaekJoon] 백준 5639번 : 이진 검색 트리

5639번 : 이진 검색 트리

처음엔 전위순회를 받아와 트리를 만든 뒤 후위순회를 하는 방식으로 풀었는데 시간초과가 발생했다.

정석적인 방법인데 시간초과가 발생해 당황했지만 괜히 전위순회를 입력으로 준게 아닐 것 같아 계속 방법을 찾아봤다.

이렇게 기준 값보다 작은 배열, 큰 배열을 나누고 또 거기서 계속 반복을 하면 됐다.

병합정렬과 비슷한 느낌..

그런데 index 처리가 너무 헷갈렸었는데 [Python]트리 백준 5639 덕분에 풀 수 있었던 문제였다.

알고리즘을 생각해도 구현을 못 해서 답답했었다..

---

import sys


def postOrder(start, end):
	if start > end:
		return

	pivot = end + 1
	for i in range(start + 1, end + 1):
		if data[i] > data[start]:
			pivot = i
			break

	postOrder(start + 1, pivot - 1)
	postOrder(pivot, end)
	print(data[start])


sys.setrecursionlimit(10 ** 9)
data = []
while True:
	try:
		data.append(int(input()))
	except:
		break

postOrder(0, len(data) - 1)