전위 순회, 중위 순회 순서가 주어지면 후위 순회 순서를 구하는 문제이다. 예전에 동일한 문제를 풀어본 적이 있어서 어떻게 푸는지는 알았다. 근데 시간이 이렇게 오래 걸릴 줄은 몰랐다…
2. 이론 세우기
우선 전위 순회는 가장 앞에 있는 노드가 루트이다. 또 중위 순회는 루트를 기준으로 왼쪽은 루트의 왼쪽 자식, 오른쪽은 루트의 오른쪽 자식으로 나뉜다. 재귀 함수를 이용해 왼쪽 자식, 오른쪽 자식을 출력한 뒤 루트를 출력하는 함수를 만들면 된다.
처음에는 재귀 함수로 전달하는 루트 노드를 노드 번호로 했었는데, 재귀호출 시 전위 순회[후위 순회[루트번호] + 1] 이런 식의 코드가 나오게 되었고 n이 범위를 벗어나는 경우 인덱스 오류가 났다. 이후부터 머리가 너무 아파서 그냥 예외처리 대신 인덱스로 루트를 넘겨주는 식으로 코드를 짰다.
3. 이론 검증하기
루트 노드의 왼쪽 자식은 전위 순회에서 루트 인덱스 + 1에 존재한다. 또 루트 노드의 모든 왼쪽 자손들은 중위 순회에서 루트가 위치한 부분의 왼쪽에 위치한다.
pre에서의 위치(인덱스)를 기준으로 루트를 선정한다.
오른쪽 자식은 pre에서 루트의 바로 오른쪽에 존재한다. 즉 pre[n] + 1이다.
왼쪽 자식은 pre에서 루트의 모든 자손(노란 네모)을 거친 이후에 등장한다. 즉 pre[n] + len(in[n] - 1)이다.
루트 인덱스가 n - 1보다 커지면 범위를 넘어가므로 함수를 종료한다.
각 재귀 함수를 호출할 때 볼 범위를 in 기준으로 넘겨준다. 즉 파란 네모를 루트로 하고 왼쪽 자손을 찾는 재귀 함수를 호출하면, 해당 함수는 in의 노란 네모 부분만을 신경쓴다는 것을 알려주는 것이다.
시작 인덱스와 종료 인덱스가 같아지면 리프 노드이므로 함수를 종료한다.
4. 의사코드 작성하기
**- 재귀 함수(전위 순회에서 루트의 인덱스, 시작 인덱스, 종료 인덱스)**
범위를 벗어나면 함수를 종료한다.
리프 노드이면 현재 노드를 출력에 추가하고 종료한다.
재귀 함수(n + 1, 시작 인덱스, in에서의 루트 위치 - 1)로 왼쪽 자식을 탐색한다.
왼쪽 자식 개수를 센다.
재귀 함수(n + 왼쪽 자식 개수 + 1, in에서의 루트 위치 + 1, 종료 인덱스)로 오른쪽 자식을 탐색한다.
현재 노드를 출력에 추가하고 종료한다.
5. 복기하기
import sys
input = sys.stdin.readline
def postOrder(n, si, ei):
if si > ei or n >= N:
return
if si == ei:
result.append(p[n])
return
postOrder(n + 1, si, inO[p[n]] - 1) # 왼쪽 자식 탐색
leftCnt = inO[p[n]] - si
postOrder(n + leftCnt + 1, inO[p[n]] + 1, ei) # 오른쪽 자식 탐색
result.append(p[n])
return
def solution():
global N, preO, inO, visited, p, i, result
N = int(input())
p = list(map(int, input().split()))
i = list(map(int, input().split()))
preO = dict()
inO = dict()
for x in range(N):
preO[p[x]] = x
inO[i[x]] = x
visited = [False] * (N + 1)
result = []
postOrder(0, 0, N - 1)
print(*result)
t = int(input())
for _ in range(t):
solution()
그림으로 그려보는 것을 계속 연습해야겠다. 특히 인덱스와 관련된 문제는 한끝차이로 오류가 발생하는 경우가 많으니까 더 세심하게 설계해야 할 것 같다.
