약 50분의 풀이시간 끝에 처음 작성한 풀이는 다음과 같다.
이때, 대부분은 시간초과가 나고, 런타임에러도 몇 개 같이 나왔다.
런타임에러의 원인은 sys.setrecutionlimit(10**6)을 적지 않아서였다.
재귀를 이용할 때 항상 생각하자.
node_num_info = None
class TreeNode:
def __init__(self, node_num, left, right):
self.node_num = node_num
self.left = left
self.right = right
def tree_make(left_x, right_x, upper_y):
'''
left_x 초과 right_x 미만인 x범위이고 upper_y 미만인 y범위의 서브트리 반환
'''
global node_num_info
# 시간초과 날듯
for y in reversed(range(upper_y)):
for x in range(left_x+1, right_x):
node_num = node_num_info[x][y]
if node_num:
new_x, new_y = x,y
left = tree_make(left_x, new_x, new_y)
right = tree_make(new_x, right_x, new_y)
return TreeNode(node_num, left, right)
return None # 해당 범위의 노드가 없으면 None으로 반환
def preorder(node, preorder_list):
preorder_list.append(node.node_num)
if node.left:
preorder(node.left, preorder_list)
if node.right:
preorder(node.right, preorder_list)
def postorder(node, postorder_list):
if node.left:
postorder(node.left, postorder_list)
if node.right:
postorder(node.right, postorder_list)
postorder_list.append(node.node_num)
def solution(nodeinfo):
global node_num_info
answer = [[]]
min_x = min(x for x,y in nodeinfo)
max_x = max(x for x,y in nodeinfo)
max_y = max(y for x,y in nodeinfo)
node_num_info = [[0]*(max_y+1) for _ in range(max_x+1)]
for i,(x, y) in enumerate(nodeinfo):
node_num_info[x][y] = i+1
# 트리 제작
root_tree = tree_make(min_x-1, max_x+1, max_y+1)
now_node = root_tree
preorder_list = []
preorder(now_node, preorder_list)
now_node = root_tree
postorder_list = []
postorder(now_node, postorder_list)
return [preorder_list, postorder_list]이후 50분의 추가 고민(with 다른 풀이 참조) 이후 정답처리된 코드는 다음과 같다.
핵심은 for문에서 존재하는 x,y좌표에 대해서만 순회하는 것이다.
x,y 범위에 대해 모두 for문을 돌게 되면 10000*10000인데, 존재하는 x,y좌표만 돌면 10000이기 때문이다.
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6) # !런타임 에러 방지
node_num_info = None
reversed_y_list = None
class TreeNode:
def __init__(self, node_num, left, right):
self.node_num = node_num
self.left = left
self.right = right
def tree_make(left_x, right_x, upper_y):
'''
left_x 초과 right_x 미만인 x범위이고 upper_y 미만인 y범위의 서브트리 반환
'''
global node_num_info, reversed_y_list
# 시간초과 나던 곳
for y in reversed_y_list: # !존재하는 y만 돌아야됨
if y < upper_y:
for x, node_num in node_num_info[y]: # !존재하는 x만 돌아야됨
if left_x < x < right_x:
new_x, new_y = x,y
left = tree_make(left_x, new_x, new_y)
right = tree_make(new_x, right_x, new_y)
return TreeNode(node_num, left, right)
return None # 해당 범위의 노드가 없으면 None으로 반환
def preorder(node, preorder_list):
preorder_list.append(node.node_num)
if node.left:
preorder(node.left, preorder_list)
if node.right:
preorder(node.right, preorder_list)
def postorder(node, postorder_list):
if node.left:
postorder(node.left, postorder_list)
if node.right:
postorder(node.right, postorder_list)
postorder_list.append(node.node_num)
def solution(nodeinfo):
global node_num_info
global reversed_y_list
min_x = min(x for x,y in nodeinfo)
max_x = max(x for x,y in nodeinfo)
max_y = max(y for x,y in nodeinfo)
reversed_y_list = list(sorted(set(y for x,y in nodeinfo), reverse=True))
node_num_info = defaultdict(list)
for i,(x, y) in enumerate(nodeinfo):
node_num_info[y].append((x,i+1)) # x좌표, 노드 번호
# 트리 제작
root_node = tree_make(min_x-1, max_x+1, max_y+1)
now_node = root_node
preorder_list = []
preorder(now_node, preorder_list)
now_node = root_node
postorder_list = []
postorder(now_node, postorder_list)
return [preorder_list, postorder_list]
성장!