문제 링크

https://programmers.co.kr/learn/courses/30/lessons/42892

문제 설명

• 트리가 좌표들로 주어짐
• 아래 조건을 만족
  • 자식 노드의 y 값은 항상 부모 노드보다 작다.
  • 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
  • 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.

풀이

• y로 내림차순 정렬한 후 순서대로 트리에 insert
• preorder
• postorder

느낀 점

• 처음에 한번에? 트리를 만들어보려 했는데 실패
  • 정렬하고 x, y 좌표에 따라 자식 노드 정하는 식으로?
  • 이분 탐색 등
• 그냥 위에서부터 insert 해주면 자기 자리 찾아간다는데 못 떠올렸음
• insert 할 때 10000(노드 개수) x 1000(최대 높이) 정도 걸릴 것 같다

코드

import sys
sys.setrecursionlimit(10000)


def solution(nodeinfo):
    # 트리 생성
    nodeinfo = sorted(enumerate(nodeinfo), key=lambda x: -x[1][1])
    root = [nodeinfo[0], [], []]
    for i in range(1, len(nodeinfo)):
        insert(root, nodeinfo[i])
    # 순회
    answer = [[], []]
    preorder(answer, root)
    postorder(answer, root)
    return answer


def insert(curr, node):
    parent, left, right = curr
    if parent[1][0] > node[1][0]:
        if left:
            insert(left, node)
        else:
            left += [node, [], []]
    else:
        if right:
            insert(right, node)
        else:
            right += [node, [], []]


def preorder(answer, curr):
    parent, left, right = curr
    answer[0].append(parent[0] + 1)
    if left:
        preorder(answer, left)
    if right:
        preorder(answer, right)


def postorder(answer, curr):
    parent, left, right = curr
    if left:
        postorder(answer, left)
    if right:
        postorder(answer, right)
    answer[1].append(parent[0] + 1)