문제
접근
문제를 최대한 꼼꼼히 읽고, 정확히 이해하는게 얼마나 중요한지 알게된 문제이다.
전위, 후위 순회는 쉽지만, 주어진 정보들로 어떻게 트리를 만드느냐가 관건이다.
문제를 다풀고 찾아보니 굉장히 간결하게 트리를 만들어내는 고수분들이 정말 많은 것 같다..
나는 그냥 정석대로 만들었다.
루트 노드를 붙이고, 크기를 비교하며 하나씩 내려오며 노드들을 이어갔다.
편하게 하려면 트리를 만들기 전에 데이터를 정렬해줄 필요가 있다.
y를 내림차순으로 정렬해주고, 그 안에서 x를 오름차순으로 정렬해주면 순서대로 돌면서 한번에 트리를 만들어낼 수 있다.
나는 노드를 이어갈 때, 해당 트리의 y(level)이 규칙대로 안지켜지면 어쩌지란 고민 때문에 많이 해맸다.
단순히 x값을 비교하며 트리에 삽입하기에는 이미 트리의 깊이인 y가 주어져있는데 이 규칙이 안지켜져서,
삽입할 위치를 찾고 해당 위치의 깊이가 y와 맞는지 확인해주려고 했다.
나중에 알았지만, 내가 고민했던 부분은 문제에서 주어지지 않는 경우였다…
그리고 코드는 정상적인거 같은데, 자꾸 일부 테스트에서 오류가 나서 찾아보니 재귀 호출이 너무 많아져서 나는 오류였다.
1
2
import sys
sys.setrecursionlimit(10**6)
코드에 이 구문을 추가해서 재귀 호출 제한을 늘려줘야 한다.
코드
- 파이썬 코드
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import sys
sys.setrecursionlimit(10**6)
class Tree:
def __init__(self, data):
self.x=data[0]
self.y=data[1]
self.idx=data[2]
self.left=None
self.right=None
def solution(nodeinfo):
for i in range(len(nodeinfo)):
nodeinfo[i].append(i+1)
nodeinfo.sort(key = lambda x: (-x[1], x[0]))
root = None
for node in nodeinfo:
if root == None:
root = Tree(node)
else:
x = node[0]
tmp = root
while True:
if x < tmp.x:
if tmp.left:
tmp = tmp.left
continue
else:
tmp.left = Tree(node)
break
elif x > tmp.x:
if tmp.right:
tmp = tmp.right
continue
else:
tmp.right = Tree(node)
break
pre = []
post = []
order(root, pre, post)
return [pre,post]
def order(node, pre, post):
pre.append(node.idx)
if node.left:
order(node.left, pre, post)
if node.right:
order(node.right, pre, post)
post.append(node.idx)