[백준5639번] 이진 검색 트리 / Python3

문제

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

• 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력 1

50
30
24
5
28
45
98
52
60

예제 출력 1

5
28
24
45
30
60
52
98
50

시간 제한	메모리 제한
1 초	256 MB

문제 접근

• [초기 접근]

  • 배열을 이용하여 트리 구조를 만들어 입력으로 주어진 전위순회 순서를 이용하여 이진탐색트리를 채워넣은 뒤 후위 순회를 돌리는 코드로 작성하였었다.

    • 초기구현코드

        nums = []
        while True:
            try:
                num = int(input())
                nums.append(num)
            except:
                break
      
        q = [None for _ in range(100000000)]
        before = 1
        for i in range(len(nums)):
            num = nums[i]
      
            # 초기 루트 설정
            if not q[1]:
                q[1] = num
                continue
      
            if num > nums[i - 1]:
                while q[before] < num:
                    if before == 1:
                        break
      
                    if q[before // 2] > num:
                        break
                    before //= 2
      
                before = before * 2 + 1
                while q[before]:
                    before = before * 2 + 1
            else:
                before *= 2
      
            q[before] = num
      
        def post_travel(node):
            if q[node * 2]:
                post_travel(node * 2)
            if q[node * 2 + 1]:
                post_travel(node * 2 + 1)
            print(q[node])
      
        post_travel(1)

  • 초기 접근 방식의 문제점은 메모리 초과였다. → 문제에서도 알 수 있듯이 노드의 수는 최대 10,000개가 될 수 있기때문에 배열을 이용해 트리 구조를 만든다면 왼쪽 자식만 쭉 가지게 되는 경우에는 트리의 높이가 2의 10000제곱까지 필요하게 된다.

• [해답을 통한 접근]

  • 입력으로 주어진 전위순회를 ”루트” - “왼쪽” - “오른쪽”로 쪼개어 후위순회를 위한 재귀 입력으로 넣어주면 되었다. → 루트는 입력의 0번 인덱스 값이며 배열을 차례대로 순회하며 루트의 값보다 커지는 순간 오른쪽의 노드들이므로 쪼개는 것이 가능하다.

      [루트, ...왼쪽..., ...오른쪽...] => [루트], [왼쪽], [오른쪽]

  • 문제의 이름을 보고 너무 단순하게 입력받은대로 우선순위 큐를 만들어내겠다는 생각에 사로 잡혀 위의 생각은 해보지를 못했던 것 같다. 은근 참신한 문제로 느껴졌다.

코드

import sys
sys.setrecursionlimit(10000)

nums = []
while True:
    try:
        num = int(input())
        nums.append(num)
    except:
        break

def post_travel(arr):
    root = arr[0]

    left_start = 1
    right_start = len(arr)
    for i in range(1, len(arr)):
        if root < arr[i]:
            right_start = i
            break

    left_arr = arr[left_start:right_start]
    if left_arr:
        post_travel(left_arr)

    right_arr = arr[right_start:]
    if right_arr:
        post_travel(right_arr)
    print(root)

post_travel(nums)