길 찾기 게임

문제

---

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

코딩테스트 연습 - 길 찾기 게임

 

 

나의 풀이

---

preorder와 postorder로 트리를 순회하는 것은 쉽다.(모르면 검색을 해보면 금방 나올 것이다.) 이 문제의 핵심은 주어진 정보로 트리를 얼마나 잘 구현하는가이다.

1. nodeinfo를 y좌표에 대해 내림차순, x좌표에 대해 오름차순으로 정렬한다.
2. 정렬된 nodeinfo를 순회하며 각 노드의 자리를 찾아 삽입한다.
   
   1. 문제에서 주어진 조건 중 왼쪽 서브트리의 모든 노드들의 x좌표는 부모 노드의 x좌표보다 작고, 오른쪽 서브트리는 크다는 조건을 사용한다.
   2. root부터 시작해 아래로 내려가면서 위의 조건을 사용해 자리를 찾아간다.

 

코드

---

import sys
sys.setrecursionlimit(10**6)

pre, post = [], []

class Tree:
    def __init__(self, nodeid, data, left=None, right=None):
        self.id = nodeid
        self.data = data
        self.left = left
        self.right = right

def preorder(root):
    if not root:
        return
    pre.append(root.id)
    if root.left:
        preorder(root.left)
    if root.right:
        preorder(root.right)

def postorder(root):
    if not root:
        return
    if root.left:
        postorder(root.left)
    if root.right:
        postorder(root.right)
    post.append(root.id)

def solution(nodeinfo):
    answer = []
    sorted_nodeinfo = sorted(nodeinfo, key = lambda x : (-x[1],x[0]))
    # tree 구성하기
    root = None
    for node in sorted_nodeinfo:
        if not root:
            root = Tree(nodeinfo.index(node)+1,node)
        else:
            cur = root
            while True:
                if node[0] < cur.data[0]:
                    if not cur.left:
                        cur.left = Tree(nodeinfo.index(node)+1,node)
                        break
                    else:
                        cur = cur.left
                        continue
                elif node[0] > cur.data[0]:
                    if not cur.right:
                        cur.right = Tree(nodeinfo.index(node)+1,node)
                        break
                    else:
                        cur = cur.right
                        continue

    preorder(root)
    postorder(root)
    return [pre, post]