[BOJ] 2263번 : 트리의 순회(이분 탐색, 재귀)

목차

접근

`n`개의 정점을 가는 이진 트리의 정점에서 1 ~ n까지 중복 없이 번호가 매겨져 있다.

이런 이진 트리에서 인오더(중위순회)와 포스트오더(후위순회)가 주어졌을 때, 프리오더(전위순회)를 구하는 문제다.

 

정말 많이 틀리고, 시간이 들었다. 여러 개선점에 대해서 생각해보는 시간이었다.

먼저 기본적인 접근에 대해서 생각해보자.

• 중위순회는 이진트리를 Left - Mid - Right 순으로 탐색을 진행한다. 
• 후위순회는 이진트리를 Left - Right - Mid 순으로 탐색을 진행한다.

그럼 맨 처음 주어진 각각의 순회의 결과에서 후위순회의 마지막 결과값이 처음 트리의 Mid의 값이라는 것을 알 수 있다. 그럼 아래와 같으 과정을 거치면, 트리를 재귀적으로 분해해나갈 수 있다.

• 위에서 구한 Mid 값의 인덱스를 전위순회의 결과에서 찾는다.
• 처음부터 해당 인덱스 전까지는 Left 트리의 순회결과.
• 해당 인덱스 후부터 끝까지는 Right 트리의 순회결과.
• 중위순회, 후위순회 모두 트리의 순회결과의 갯수는 같아야하기에, 후위순회의 결과 또한 분해할 수 있다.
  • 처음부터 해당 인덱스 전까지는 후위순회의 Left 순회결과.
  • 해당 인덱스부터 마지막 바로 전까지는 Right 순회결과.
• 재귀함수는 Mid 값 출력 -> Left 트리 탐색 -> Right 트리 탐색 으로 위와 같은 과정을 수행해나간다.

Mid가 발견된 인덱스와, 각각의 탐색의 순서를 생각하여 중위순회와 후위순회 결과를 이용해서 재귀적으로 트리의 전위순회를 진행할 수 있다.

 

 

해결

첫번째 시도

그냥 위와 같은 개념을 구체화한 상태로 배열을 슬라이싱해서 넘겨주는 방식으로 재귀함수를 구현했다.

import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline

n = int(input())
inorder = list(map(int, input().split())) # left - mid - right
postorder = list(map(int, input().split())) # left - right - mid
# preorder: mid - left - right 

def dfs(in_order, post_order):
    if len(in_order) == 1:
        print(in_order[0], end=" ")
        return
    
    if not in_order or not post_order:
        return
    
    mid_idx = in_order.index(post_order[-1])
    left_tree = in_order[:mid_idx]
    right_tree = in_order[mid_idx+1:]
    
    print(in_order[mid_idx], end=" ")
    dfs(left_tree, post_order[:mid_idx])
    dfs(right_tree, post_order[mid_idx:-1])
    
dfs(inorder, postorder)

 

메모리 초과가 발생했다. 당연할법도 한게, 재귀적으로 진행을 하면서 슬라이싱한 결과들이 다 메모리에 저장될 것이다. 그럼 엄청나게 많은 메모리가 할당될 것이고, 그럼 터질 수 밖에 없다.

 

두번째 시도

중위순회의 시작점과 후위순회의 시작점 또 트리의 순회결과의 길이를 넘겨주어서 해결하는 방식으로 구현했다. 메모리가 자꾸 넘쳐나기에, 원래의 결과에서 인덱스만 가지고 조작을 하는 방식으로 구현을 해야겠다고 마음을 먹고 시작했다. 근데 자꾸 메모리가 또 터졌다.

import sys

sys.setrecursionlimit(10**5)
input = sys.stdin.readline

n = int(input())

inorder = list(map(int, input().split())) # left - mid - right
postorder = list(map(int, input().split())) # left - right - mid
# preorder: mid - left - right 

def dfs(in_order_st, post_order_st, length):
    if not length:
        return
    if length == 1:
        print(inorder[in_order_st], end=" ")
        return
    
    
    left_length = inorder.index(postorder[post_order_st:post_order_st+length][-1]) - in_order_st
    
    print(inorder[in_order_st+left_length], end=" ")
    dfs(in_order_st, post_order_st, left_length)
    dfs(in_order_st + left_length+1, post_order_st + left_length, length-left_length-1)
    
dfs(0, 0, n)

 

터진 이유는 중위순회에서 Mid 인덱스를 찾을 때, 후위순회의 결과를 슬라이싱해서 사용하는 방식을 썻다. 슬라이싱이 하나만 들어가도 `O(k)`만큼의 시간복잡도가 추가 되는 것이기에, 또 시간초과가 발생했다.

 

결론적으로는 슬라이싱을 모두 없애고, 후위순회의 마지막 인덱스로만 접근해서 Mid 인덱스를 구하는 방식으로 아래와 같은 코드로 통과하였다. 또한 PyPy3로 제출해야 통과가 되더라.. 

코드

import sys

sys.setrecursionlimit(10**5)
input = sys.stdin.readline

n = int(input())

inorder = list(map(int, input().split())) # left - mid - right
postorder = list(map(int, input().split())) # left - right - mid
# preorder: mid - left - right 

def dfs(in_order_st, post_order_st, length):
    if not length:
        return
    if length == 1:
        print(inorder[in_order_st], end=" ")
        return
    
    
    left_length = inorder.index(postorder[post_order_st+length-1]) - in_order_st
    
    print(inorder[in_order_st+left_length], end=" ")
    dfs(in_order_st, post_order_st, left_length)
    dfs(in_order_st + left_length+1, post_order_st + left_length, length-left_length-1)
    
dfs(0, 0, n)