프로그래머스 - 길 찾기 게임

2019 카카오 블라인드 채용 문제이다.

레벨은 3이다.

 

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

프로그래머스

문제에서 힌트? 인지는 모르겠지만 이진트리라고 말을 했다.

그래서 이진트리를 구현했다.

먼저 입력 값을 정렬을 해주었다.

첫 번째 값이 root값이 나온다.

그 root값을 기준으로 x좌표값을 비교하여 이진트리를 완성해 간다.

 

전위연산 후위연산은 재귀로 쉽게 구현할 수 있다.

 

 

import sys
sys.setrecursionlimit(10**6)

class node:
    def __init__(self,item,y,x):
        self.item = item
        self.y = y # 얘는 필요가 없음
        self.x = x
        self.left = None
        self.right = None
class BT():
    def __init__(self, root = None):
        self.root = root
    def push(self, data):
        ptr_Node = self.root
        temp_node = self.root
        while ptr_Node is not None:
            temp_node = ptr_Node
            if ptr_Node.x > data.x:
                ptr_Node = ptr_Node.left
            else:
                ptr_Node = ptr_Node.right
        if temp_node.x > data.x:
            temp_node.left = data#주소값 참조
        else:
            temp_node.right = data
    def preorder(self):
        answer = []
        def _preorder(node):
            answer.append(node.item)
            if node.left:
                _preorder(node.left)
            if node.right:
                _preorder(node.right)
        _preorder(self.root)
        return answer
    def postorder(self):
        answer = []
        def _postorder(node):
            if node.left:
                _postorder(node.left)
            if node.right:
                _postorder(node.right)
            answer.append(node.item)
        _postorder(self.root)
        return answer


def solution(nodeinfo):
    answer = []
    sort_info = sorted(nodeinfo, key= lambda x : (-x[1],x[0]))
    Tree = BT()
    for idx, i in enumerate(sort_info):
        data = node(nodeinfo.index(i)+1,i[1],i[0])
        if idx == 0:
            Tree.root = data
        else:
            Tree.push(data)
    answer.append(Tree.preorder())
    answer.append(Tree.postorder())
    return answer