정보
문제 바로가기 [클릭]
난이도: Gold2
관련 개념: #트리 #분할정복 #재귀
조건
시간 제한 | 메모리 제한 |
---|---|
5 초 | 128 MB |
문제
n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.
출력
첫째 줄에 프리오더를 출력한다.
예제 입출력 1
입력
1
2
3
3
1 2 3
1 3 2
출력
1
2 1 3
코드(파이썬)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import sys
sys.setrecursionlimit(100001)
def check(in_start, in_end, post_start, post_end):
global result
root_value = postorder[post_end]
l_length = inorder.index(root_value) - in_start
result.append(root_value)
if l_length > 1:
check(in_start, in_start+l_length-1, post_start, post_start+l_length-1)
elif l_length == 1:
result.append(inorder[in_start])
if in_start+l_length+1 < in_end:
check(in_start+l_length+1, in_end, post_start+l_length, post_end-1)
elif in_start+l_length+1 == in_end:
result.append(inorder[in_end])
n = int(sys.stdin.readline())
inorder = sys.stdin.readline().split()
postorder = sys.stdin.readline().split()
result = []
check(0, n-1, 0, n-1)
print(*result)
특이사항
- 분할정복을 위해 구역을 나눠서 해결하는 것은 맞음
- 도저히 그 다음 아이디어가 생각나지 않아 pypy로 제출 후 풀이 확인
- 내 코드(331,124KB, 15,084ms)에 비해 우수한 코드(바로가기, 161,052KB, 332ms)와 비교
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
from sys import stdin, setrecursionlimit setrecursionlimit(10 ** 9) n = int(stdin.readline()) inorder = list(map(int, stdin.readline().split())) postorder = list(map(int, stdin.readline().split())) inorder_index = [0] * (n + 1) for i in range(n): inorder_index[inorder[i]] = i answer = [] def preorder(in_start, in_end, post_start, post_end): if (in_start > in_end) or (post_start > post_end): return parent = postorder[post_end] answer.append(parent) left = inorder_index[parent] - in_start right = in_end - inorder_index[parent] preorder(in_start, in_start + left - 1, post_start, post_start + left - 1) preorder(in_end - right + 1, in_end, post_end - right, post_end - 1) preorder(0, n - 1, 0, n - 1) print(*answer)
- 인덱스 확인
- 기존: index 메서드 이용
- 개선: inorder_index 리스트를 생성해 inorder 인덱스 확인을 O(1)에 해결
참고문헌
-
Comments powered by Disqus.