[BOJ, Python] 5639번_이진 검색 트리

백준 5639-골드 4

문제를 간단하게 요약하면 '전위 순회 결과를 받아서 후위 순회 결과로 변환하여 출력하라'이다.

---

생각보다 쉬울거라 생각했던 이 문제에서 꽤나 애를 먹었다.
우선 생각한 풀이는 2가지이다.

1. 전위 순회 결과를 트리 형태로 만들어서 후위 순회 결과를 찾는다.
2. 전위 순회 결과에서 후위 순회 결과로 변환하는 규칙을 찾아서 적용한다.

2번 풀이가 맞는 풀이라고 생각해 규칙을 찾아보려고 노력했다.
여기서 트리에 대한 지식의 부족을 느꼈다.

분명 전위 순회, 중위 순회, 후위 순회를 하는 방법은 알지만 아무리 봐도 규칙이 보이지 않았다.

그래서 우선 하나하나 접근하기로 했다.

전위 순회 결과가 [5, 3, 1, 4, 8, 6, 9]일 경우를 생각해보자.
우선 후위 순회 결과는 [1,4,3,6,9,8,5]이다.

1. 루트는 5이고, [3, 1, 4]는 왼쪽 서브트리, [8, 6, 9]는 오른쪽 서브트리이다.
2. 왼쪽 서브트리 [3, 1, 4]에서 루트는 3이고 [1]이 왼쪽 서브트리, [4]가 오른쪽 서브트리이다.
3. 오른쪽 서브트리 [8, 6, 9]에서 루트는 8이고 [6]이 왼쪽 서브트리, [9]가 오른쪽 서브트리이다.

문제에도 나와있는 것처럼 후위 순회 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트 순으로 출력한다.

그렇다면 위처럼 각 서브트리를 쪼개고 쪼개서 왼쪽 서브트리부터 하나씩 출력하면 그게 곧 후위 순회가 아닐까?

해당 생각을 바탕으로 결과를 찾아보니 [1,4,3,6,9,8,5]가 나왔다.
즉, 후위 순회 결과가 똑같이 나왔다!

이제 문제를 풀이 이론도 정립했으니 코드로 구현해보자.

전체 풀이 코드

import sys
input = lambda: sys.stdin.readline().rstrip()
#recursion error 방지
sys.setrecursionlimit(10**9)

arr = []
while True:
    try:
        x = int(input())
        arr.append(x)
    except:
        break

def sol(arr):  
    if len(arr) == 0: // 트리의 길이가 0이라면 return
        return
    
    tempL, tempR = [], [] // 왼쪽 서브트리, 오른쪽 서브트리
    root = arr[0] // 루트

    for i in range(1, len(arr)):
        if arr[i] > root: // 변수의 값이 루트보다 커진다면
            tempL = arr[1:i] # 그 이전까지의 값이 왼쪽 서브트리
            tempR = arr[i:] # 이후부터의 값이 오른쪽 서브트리
            break
    else:
        tempL = arr[1:]
    sol(tempL) # 왼쪽 서브트리 재귀
    sol(tempR) # 오른쪽 서브트리 재귀
    print(root)

sol(arr)

결과

첫번째 시도에서는
recursion error를 고려하지 않아서 recursion error가 발생했다.

sys.setrecursionlimit(10**9)를 추가해주면 recursion error를 방지할 수 있다.