트리 : 이진 검색 트리(백준 5639번)

▶ 문제 : https://www.acmicpc.net/problem/5639

5639번: 이진 검색 트리

##### 문제 ##### 
# 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.
# 노드의 왼쪽 서브 트리에 있는 모든 노드의 키는 노드의 키보다 작다.
# 노드의 오른쪽 서브 트리에 있는 모든 노드의 키는 노드의 키보다 크다.
# 왼쪽, 오른쪽 서브 트리도 이진 검색 트리이다.
# 이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 
# 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

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

##### 출력 #####
# 입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

 

▶ 접근 방법

전위 순회와 후위 순회의 개념을 이해한 후, 문제에 접근해야 했다.

입력 값으로 주어진 전위 순회의 결과는 [50 30 24 5 28 45 98 52 60] 이다.
이때, 개별 트리의 루트 노드를 먼저 출력하는 전위 순회의 특성상
가장 먼저 출력된 값 50은 최상단 루트 노드의 값이다.
이를 기준으로 작은 값들은 루트의 왼쪽 서브 트리에 포함되고,
큰 값들은 루트의 오른쪽 서브 트리에 포함된다.
이에 따라 상기 전위 순회의 결과를 분류해보면,
루트 [50], 왼쪽 서브 트리 [30 24 5 28 45], 오른쪽 서브 트리 [98 52 60]로 나누어볼 수 있다.

이제 왼쪽 서브 트리에 [30], 오른쪽 서브 트리에 [98]만 있다고 가정해보자.
해당 경우, 전위 순회의 출력 순서는 루트 [50], 왼쪽 [30], 오른쪽 [98] 순이다.
그런데 후위 순회는 출력 순서가 왼쪽 [30], 오른쪽 [98], 루트[50] 순이다.

따라서, 원래 결과의 왼쪽 서브 트리 먼저 출력하고 이후 오른쪽 서브 트리, 루트를 출력하면 된다.
중요한 것은 각각의 서브 트리 역시 후위 순회 방식으로 출력해야 한다는 것이다.
이에 재귀적인 방식으로 서브 트리에 해당하는 값들을 탐색한 후 결과를 출력하였다.

재귀 함수를 만들 때, 입력 값으로 들어갈 범위를 정확히 정하는 것,
후위 순회에 맞게 순서를 맞추는 것이 중요하다.

 

▶ 풀이 코드

import sys
sys.setrecursionlimit(100000)

# pre_order 결과를 일단 만든다.
pre_order = []
while True:
    try :
        pre_order.append(int(sys.stdin.readline().rstrip()))
    except:
        break


def get_post_order(pre_order):
    length = len(pre_order)

    # 들어온 값이 1개 미만이라면 그냥 그 값을 반환한다.
    if length <= 1:
        return pre_order
    
    # pre_order에 root 다음 숫자부터, root와 비교한다.
    for i in range(1, length):
        # root보다 큰 수를 기준으로 다시 함수를 호출한다.
        if pre_order[i] > pre_order[0]:
            # root보다 큰 수 전까지, 큰 수 부터 끝까지, root
            return get_post_order(pre_order[1:i]) + get_post_order(pre_order[i:]) + [pre_order[0]]
    
    return get_post_order(pre_order[1:]) + [pre_order[0]]


result = get_post_order(pre_order)
for num in result :
    print(num)

 

▶ 관련 링크

2021.11.18 - [알고리즘] - 트리(Tree)란?

2021.11.18 - [알고리즘] - BFS(Breadth First Search, 너비 우선 검색)이란?

2021.11.18 - [알고리즘] - DFS(Depth First Search, 깊이 우선 탐색)이란?

2021.11.19 - [알고리즘] - 그래프(Graph)란?

2021.11.19 - [알고리즘] - 트리 : 트리 순회(백준 1991번)