[알고리즘 연습] 길찾기 게임 (프로그래머스 lv3, 파이썬)

문제

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

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

참고

https://inuplace.tistory.com/185?category=884573

[자료구조] 트리

• 트리 구조 및 순회에 대한 이해 필요

풀이

import sys
sys.setrecursionlimit(10**6)

class Tree:
    def __init__(self,dataList):
        self.data = max(dataList,key=lambda x :x[1])
        leftList =list(filter(lambda x :x[0] < self.data[0] , dataList))
        rightList = list(filter(lambda x :x[0] > self.data[0] , dataList))
        if leftList != []:
            self.left=Tree(leftList)
        else :
            self.left=None

        if rightList != []:
            self.right=Tree(rightList)
        else :
            self.right=None

def fix(node,preList,postList):
    preList.append(node.data)
    if node.left is not None:
        fix(node.left,preList,postList)
    if node.right is not None:
        fix(node.right,preList,postList)
    postList.append(node.data)

def solution(nodeinfo):
    answer = []
    root = Tree(nodeinfo)
    postList = []
    preList = []
    fix(root,preList,postList)
    answer.append(list(map(lambda x: nodeinfo.index(x)+1 ,preList)))
    answer.append(list(map(lambda x: nodeinfo.index(x)+1 ,postList)))
    return answer

• 재귀를 이용해 트리를 초기화
• 재귀를 이용해 트리 순회
• 순회결과 도출