[트리] 백준 5639번: 이진 검색 트리 / 실버 1

https://www.acmicpc.net/problem/5639

5639번: 이진 검색 트리

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다

www.acmicpc.net

import sys
sys.setrecursionlimit(10**5)
nums = []
while True:
    try:
        a = input()
        nums.append(int(a))
    except:
        break

def divide(start, end):
    if start > end:
        return []

    if start == end:
        return [nums[start]]

    cur = nums[start]

    left_start = start + 1
    left_end = end

    for i in range(left_start, end + 1):
        if nums[i] > cur:
            left_end = i - 1
            break

    right_start = left_end + 1
    right_end = end

    l = divide(left_start, left_end)
    r = divide(right_start, right_end)
    return l+r+[cur]

ans = divide(0, len(nums)-1)
for i in range(len(ans)):
    print(ans[i])

부모 노드를 이용하여 분할해가면서 풀 수 있는 문제다.

처음엔 결과를 리스트로 반환하는 식으로 문제를 풀었는데

따로 리스트를 만들 필요없이 재귀 함수 내에서 바로바로 출력하여 문제를 풀 수도 있었다.

아래는 개선된 코드!

import sys
sys.setrecursionlimit(10**5)
nums = []
while True:
    try:
        nums.append(int(input()))
    except:
        break

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

    cur = nums[start]
    smaller = end
    for i in range(start+1, end + 1):
        if nums[i] > cur:
            smaller = i - 1
            break
    divide(start+1, smaller)
    divide(smaller+1, end)
    print(cur)

divide(0, len(nums)-1)

배운 점

- 입력 값이 몇 개인지에 대한 정보를 안주기 때문에 위의 코드처럼

try와 except를 이용하여 입력 값을 받아와야 한다.