문제 링크
풀이 과정
•
본 문제는 이진 트리를 조건에 맞게 구현하는 것이 핵심입니다. 개인적으로, 이진 트리를 직접 구현한 경험이 없어서 문제를 푸는 데 많이 애를 먹었습니다…..
•
트리를 구현할 때는 크게 두 가지 사항을 고려해야 합니다.
◦
트리를 구성하는 노드를 어떻게 정의할 것인가? 즉, 노드에 어떤 데이터를 저장할 것인가?
◦
트리 내에서, 노드 분기(branch) 기준은 무엇으로 할 것인가?
•
문제 조건에 따르면, 모든 노드의 x 좌표 값은 서로 다르다고 하였습니다.
◦
따라서, 노드 분기 기준은 노드의 x 좌표 값을 이용합니다.
◦
새로운 노드의 x 좌표 값이 현재 노드의 x 좌표 값보다 작은 경우 → 새로운 노드는 현재 노드의 왼쪽 서브트리에 위치
◦
새로운 노드의 x 좌표 값이 현재 노드의 x 좌표 값보다 큰 경우 → 새로운 노드는 현재 노드의 오른쪽 서브트리에 위치
•
기준을 점검하기 위하여, 각 노드는 좌표 데이터를 가져야합니다!
•
결과적으로, 다음과 같이 정리할 수 있습니다!
◦
노드에 어떤 데이터를 저장할 것인가? → 왼쪽 자식 노드, 오른쪽 자식 노드, 좌표
◦
노드 분기(branch) 기준은 무엇으로 할 것인가? → x 좌표
결과적으로, 의사 코드는 아래와 같이 작성할 수 있습니다.
<Solution>
노드 번호를 좌표 값에 따라 정렬한다.
- (1순위) y 좌표: 큰 값 -> 작은 값
- (2순위) x 좌표: 작은 값 -> 큰 값
정렬된 노드 번호 순으로 이진 트리를 생성한다.
생성된 이진 트리를 통해 각각 전위 순회 및 후위 순회를 수행한다.
Plain Text
복사
전체 코드
import sys
sys.setrecursionlimit(10 ** 6)
class Node:
def __init__(
self,
node_num: int,
coords: list,
left = None,
right = None
):
self.node_num = node_num
self.coords = coords
self.left = left
self.right = right
def has_left(self):
return self.left
def has_right(self):
return self.right
def make_binary_tree(nodeinfo: list) -> Node:
# 노드 번호를 정렬 -> (y 좌표가 큰 순서 + x 좌표가 작은 순서)
node_nums = [idx+1 for idx in range(len(nodeinfo))]
node_nums = sorted(
node_nums,
key=lambda x: (-nodeinfo[x-1][1], nodeinfo[x-1][0])
)
# 이진 트리 구성
root = None
for node_num in node_nums:
if not root:
root = Node(node_num, nodeinfo[node_num-1])
else:
# 분기는 항상 루트 노드에서 시작합니다!
parent = root
cur_node = Node(node_num, nodeinfo[node_num-1])
while True:
if parent.coords[0] > cur_node.coords[0]: # x 좌표 비교
if parent.has_left():
parent = parent.left
continue
parent.left = cur_node
break
else:
if parent.has_right():
parent = parent.right
continue
parent.right = cur_node
break
return root
def pre_order(root: Node, routes: list):
if root is None: return
routes.append(root.node_num)
pre_order(root.left, routes)
pre_order(root.right, routes)
def post_order(root: Node, routes: list):
if root is None: return
post_order(root.left, routes)
post_order(root.right, routes)
routes.append(root.node_num)
def solution(nodeinfo):
answer = [[], []]
# 1. 트리 구성
root = make_binary_tree(nodeinfo)
# 2. 전위 순회 실시
pre_order(root, answer[0])
# 3. 후위 순회 실시
post_order(root, answer[1])
return answer
Python
복사