문제
n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.
출력
첫째 줄에 프리오더를 출력한다.
예제 입력 1
3
1 2 3
1 3 2
예제 출력 1
2 1 3
문제 풀이
트리 순회를 구하는 법만 안다면 매우 쉬운 문제다(제약 조건은 쉽지 않다)
인오더는 LRV, 포스트오더는 LVR 의 형태로 노드가 출력된다.
이를 탑다운 형식의 분할정복 기법으로 푼다면 (루트 노드는 바로바로 출력해준다.) 케이크를 먹듯이 쉽게 풀 수 있다.
포스트오더의 마지막 인덱스에서 루트노드의 값을 찾고, 그 값으로 인오더의 루트노드 위치를 찾는다.
인오더의 루트노드를 찾게되면, 왼쪽 branch의 길이와 오른쪽 branch의 길이를 알게된다.
포스트오더의 branch를 분리할 수 있게 되었으니 이제 포스트오더와 인오더의 왼쪽과 오른쪽 branch를 해결한다.
포스트오더는 루트노드의 위치정보를 알고있으니 이를 이용해 루트노드의 값을 찾고, 인오더에서 이 값의 위치를 찾아내서 왼쪽과 오른쪽 branch의 길이를 알아내는 것이다.
이를 이용하면 반대로 포스트오더에서 왼쪽과 오른쪽 branch를 분리할 수 있게되니 트리를 구성할 수 있게된다. (이 과정에서 그냥 루트노드를 출력하게 되면 안 놀랍게도 프리오더의 출력과 같다.)
가장 쉽게 날로 먹을 수 있는 리스트 슬라이싱으로 실험해보았다.
def tree_maker(n, inorder, postorder):
# print(inorder, postorder, n)
if n<=0:
return
root = postorder[-1]
# inorder 분리용
root_idx = inorder.index(root)
print(root, end=' ')
if n==1:
return root
right_length = n-root_idx-1
left_length = root_idx
# post order의 left right
left_postorder = postorder[:left_length]
right_postorder = postorder[left_length:-1]
# inorder의 left right
left_inorder = inorder[:root_idx]
right_inorder = inorder[root_idx+1:]
# left
tree_maker(left_length, left_inorder, left_postorder)
tree_maker(right_length, right_inorder, right_postorder)
n = int(input())
inorder = list(map(int, input().split()))
postorder = list(map(int, input().split()))
tree_maker(n, inorder, postorder)
쉽게 풀리나 했는데, 사실 입력의 크기를 간과하고 있었다.
n이 100000까지 주어지기 때문에, 메모리가 감당할 수 없을정도로 리스트 슬라이싱을 한 것이다...
또한 root_idx = inorder.index(root) 이 코드도 입력의 크기를 생각하면 간과할 수 없다.
입력의 크기 때문에 실행시간이 길어지기 때문에, 추가적인 조치가 필요했다.
따라서 메모리를 최소한으로 사용하기 위해 리스트를 매개변수로 나눠주는 대신 인덱스의 시작값과 끝값을 이용하는 방법을 생각했다.
그리고 n은 branch length로 쓰이기 때문에 헷갈려서 매개변수 이름을 바꿔줬다.
def tree_maker(b_l, in_idx, post_idx):
root_val = postorder[post_idx[-1]-1]
in_root_idx = 0
for i in range(in_idx[0], in_idx[1]):
if inorder[i] == root_val:
in_root_idx = i; break
# print(b_l, in_idx, post_idx, root_val)
print(root_val, end=' ')
if b_l == 1: return
inorder_left = (in_idx[0], in_root_idx)
inorder_right = (in_root_idx+1, in_idx[1])
left_length = max(in_root_idx-in_idx[0],0)
right_length = max(in_idx[1]-in_root_idx-1,0)
postorder_left = (post_idx[0], post_idx[0]+left_length)
postorder_right = (post_idx[0]+left_length, post_idx[-1]-1)
if left_length: tree_maker(left_length, inorder_left, postorder_left)
if right_length: tree_maker(right_length, inorder_right, postorder_right)
n = int(input())
inorder = list(map(int, input().split()))
postorder = list(map(int, input().split()))
tree_maker(n, (0,n), (0,n))
# tree_maker(n, inorder, postorder)
타임아웃에 걸렸다.
재귀 에러가 났었던 제출 이후 input() 대신 sys.stdin.readline()으로 바꿔줬음에도 시간 초과가 발생했었다. (재귀 제한도 10**6으로 늘렸다.)
왜 그랬는지 생각해보니 재귀를 할 때마다 트리의 길이만큼 순회해가며 인오더에서 루트노드의 위치값을 찾는 것 때문이었다.
나름 메모리 절약한다고 저렇게 만들었는데 다시 생각해보니 저 함수 안에서만 O(n)이 되는 끔찍한 코드였다.
미리 딕셔너리를 이용해 인오더에서 노드의 값과 인덱스를 기록한 뒤, 함수 내에서 딕셔너리를 사용하는 것으로 바꾸어 주었다.
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
def tree_maker(b_l, in_idx, post_idx):
root_val = postorder[post_idx[-1]-1]
in_root_idx = order_dict[root_val]
print(root_val, end=' ')
if b_l == 1: return
inorder_left = (in_idx[0], in_root_idx)
inorder_right = (in_root_idx+1, in_idx[1])
left_length = max(in_root_idx-in_idx[0],0)
right_length = max(in_idx[1]-in_root_idx-1,0)
postorder_left = (post_idx[0], post_idx[0]+left_length)
postorder_right = (post_idx[0]+left_length, post_idx[-1]-1)
if left_length: tree_maker(left_length, inorder_left, postorder_left)
if right_length: tree_maker(right_length, inorder_right, postorder_right)
n = int(input())
inorder = list(map(int, input().split()))
postorder = list(map(int, input().split()))
order_dict = {v:i for i,v in enumerate(inorder)}
tree_maker(n, (0,n), (0,n))
ez
문제 풀이 방법을 찾는 것 자체는 쉬웠지만 인덱스 값 구하는 게 난관이었다.
인덱스로 상대적인 위치나 길이를 계산할 줄 안다면 손쉽게 풀 수 있다.
- 스택으로 최적화하면 좀 더 빠르게 풀 수 있다.
