문제

Access

문제

Input으로 in-order(중위 순회)의 결과와 post-order(후위 순회)의 결과를 받고 pre-order(전위 순회)를 구하는 문제 입니다. 전위/중위/후위 순회를 잘 파악하고 있어야 풀 수 있는 문제 입니다.

접근

순회

중위 순회

먼저 왼쪽의 자식 노드를 탐색한 다음 현재 노드를 탐색하고, 오른쪽 자식 노드를 탐색합니다. 수도코드는 아래와 같습니다

FUNCTION IN_ORDER(TREE node)
	IN_ORDER(node.left)
	DO_SOMETHING(node.val)
	IN_ORDER(node.right)

그렇기 때문에 중위 순회의 결과는 루트 노드를 기준으로 왼쪽 자식 노드의 결과 리스트 -> 루트 노드 값 -> 오른쪽 자식 노드의 결과 리스트 순으로 출력됩니다.

후위 순회

왼쪽 -> 오른쪽 자식 노드를 탐색한 다음, 마지막으로 루트 노드의 데이터를 탐색합니다.

FUNCTION POST_ORDER(TREE node)
	POST_ORDER(node.left)
	POST_ORDER(node.right)
	DO_SOMETHING(node.val)

그렇기 때문에 중간 값은 맨 마지막에 출력됩니다.

전위 순회

루트 노드 부터 탐색한 다음 왼쪽 -> 오른쪽 순으로 탐색합니다.

FUNCTION PRE_ORDER(TREE node)
	DO_SOMETHING(node.val)
	PRE_ORDER(node.left)
	PRE_ORDER(node.right)

그렇기 때문에 중간값이 가장 먼저 출력됩니다.

목표

이 두개의 입력값들을 토대로

이걸 만드는 것이 목표입니다.

루트 노드의 값을 구하고 -> left, right 경계선을 친 다음 -> 각 left, right의 경계선 범위 안에서 재귀형태로 돌려야 합니다(분할정복). 순환의 끝에 left와 right의 값이 같게 된다면 이는 리프노드가 되므로 더이상의 재귀를 수행하지 않습니다.

알고리즘

예시

풀이

[Turn 1] Root Node -> 1

1. 우선 루트 노드의 값을 확인합니다. 중위 결과에서는 루트노드의 중간 위치가 어디인 지 알 수 없지만. 후위 결과에서는 루트노드 값이 맨 끝에 위치하기 때문에 바로 찾을 수 있습니다. 이렇게 루트 노드의 값을 확인한 다음 전위 결과 리스트에 추가합니다. 그런 다음, 루트 노드 값을 토대로 중위 결과에서의 루트노드 인덱스 값을 구합니다.
   
2. 중위 결과에서 루트노드를 중심으로 left와 right로 가른 다음 left 부터 탐색합니다.
   

[Turn 2] Root Node -> 2

1. [Turn 1] 처럼 후위 결과에서 루트 노드를 찾을 수 있습니다. 아까 전에 left, right로 갈랐고 left위치에서 맨 끝부분인 2가 루트 노드입니다. 이를 전위 결과 리스트에 추가합니다. 마찬가지로 중위 노드에서의 루트노드 인덱스 값을 구합니다.
   
2. 루트 노드를 중심으로 left, right를 가릅니다.
   

[Turn 3] Root Node -> 4, 5

1. 2를 기준으로 갈랐던 left와 right는 이제 값이 하나 뿐입니다. 즉, 4와 5는 리프노드이므로 더이상 재귀를 할 이유가 없습니다. 그대로 전위 결과에 추가하고 재귀에서 빠져나옵니다.
   

[Turn 4] Root Node -> 3

1. 루트값과 루트의 위치를 구합니다.
   
2. 그런데 루트 위치로부터 왼쪽 자식 노드가 없습니다. 왼쪽 자식 노드가 없다는 것을 확인할 수 있는 방법은 해당 범위의 왼쪽과 루트 노드의 위치가 같으면 왼쪽 자식 노드가 없다는 뜻이 됩니다. 이는 오른쪽 자식 노드의 유무 확인도 똑같이 작용합니다. 그렇기 때문에 왼쪽으로 재귀 함수를 돌릴 필요가 없습니다. 오른쪽만 확인하면 됩니다.
   

[Turn 5] Root Node -> 6

1. 해당 노드는 리프노드 입니다. 더이상 재귀 함수를 돌릴 이유가 없습니다. 전위 결과에 값을 추가하고 빠져나옵니다.
   

결과

코드

import sys
sys.setrecursionlimit(100_000_000)
input = sys.stdin.readline

N = int(input())
in_order = input()[:-1].split()
post_order = input()[:-1].split()
pre_order = []

index_map = { in_order[i]: i for i in range(len(in_order)) }

def __process(left: int, right: int, postorder_mid_idx: int):

    if left == right:
        pre_order.append(in_order[left])
    else:
        mid_val = post_order[postorder_mid_idx]
        pre_order.append(mid_val)
        mid_idx = index_map[mid_val]

        left_len, right_len = mid_idx - left, right - mid_idx

        if left_len > 0:
            __process(left, mid_idx - 1, postorder_mid_idx - 1 - right_len)
        if right_len > 0:
            __process(mid_idx + 1, right, postorder_mid_idx - 1)
__process(0, N - 1, N - 1)

print(*pre_order)

선언

in_order = input()[:-1].split()
post_order = input()[:-1].split()
pre_order = []

in_order, post_order에 각각 중위/후위 탐색 결과를 입력받고 pre_order로 전위 결과를 비어있는 리스트로 선언합니다.

치트키

후위의 맨 끝에 존재하는 루트노드의 값을 이용해 중위 결과에서의 루트노드의 위치 즉, 인덱스 값을 찾아야 합니다. 파이썬에서는 리스트에서의 인덱스 값을 구하려면 index() 함수를 사용해야 합니다. 그러나 이 함수는 $O(n)$이라는 시간이 걸리기 때문에 그냥 무턱대고 구현했다간.

이렇게 됩니다.

그렇기 때문에 중위 결과에서의 인덱스 값들을 $O(1)$ 에 탐색할 수 있게 Dict형 구조체를 따로 선언합니다.

index_map = { in_order[i]: i for i in range(len(in_order)) }

key값은 노드 값, value값은 노드 값에 대한 중위 결과에서의 인덱스 값입니다. 이렇게 구현하면 비록 메모리는 더 많이 먹겠지만, 그만큼 처리 속도가 빨라져 시간 초과를 면할 수 있게 됩니다.

함수의 시작은 당연히 배열의 전 범위를 잡고 시작합니다.

__process(0, N - 1, N - 1)

루틴

def __process(left: int, right: int, postorder_mid_idx: int):

    if left == right:
        pre_order.append(in_order[left])
    else:
        mid_val = post_order[postorder_mid_idx]
        pre_order.append(mid_val)
        mid_idx = index_map[mid_val]

        left_len, right_len = mid_idx - left, right - mid_idx

        if left_len > 0:
            __process(left, mid_idx - 1, postorder_mid_idx - 1 - right_len)
        if right_len > 0:
            __process(mid_idx + 1, right, postorder_mid_idx - 1)

parameter

• left: 현재 범위의 가장 왼쪽 (중위 결과)
• right: 현재 범위의 가장 오른쪽 (중위 결과)
• postorder_mid_idx: 루트 노드의 위치(후위 결과)

return

없음

해당 노드가 리프노드인 경우

    if left == right:
        pre_order.append(in_order[left])

left와 right의 값이 동일하다는 의미는 해당 범위가 1, 즉, 원소가 하나밖에 없다는 의미가 되므로 리프노드가 됩니다. 따라서 pre_order에 값을 추가한 다음 빠져나옵니다.

리프노드가 아닌 경우

루트노드(중간값) 처리

        mid_val = post_order[postorder_mid_idx]
        pre_order.append(mid_val)
        mid_idx = index_map[mid_val]

postorder_mid_idx 를 이용해 우선 루트 노드의 값인 mid_val을 구한 다음, pre_order에 값을 추가합니다.

그 다음 왼쪽과 오른쪽을 가르기 위해 중위 결과에서의 루트 노드 위치 mid_idx을 구합니다.

왼쪽 오른쪽 가르기

        left_len, right_len = mid_idx - left, right - mid_idx

        if left_len > 0:
            __process(left, mid_idx - 1, postorder_mid_idx - 1 - right_len)
        if right_len > 0:
            __process(mid_idx + 1, right, postorder_mid_idx - 1)

우선 루트를 기준으로 왼쪽과 오른쪽의 길이인 left_len과 right_len을 구합니다.
왼쪽/오른쪽 의 길이가 1이상인 경우만 재귀 함수를 돌립니다. 한 쪽에 아무것도 없다는 것은 더이상 자식노드가 존재하지 않기 때문입니다.