[카카오 기출] 길 찾기 게임

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

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

class Node:
    def __init__(self, val = 0, left = None, right = None):
        self.val = val
        self.left = left
        self.right = right

import collections
import sys
sys.setrecursionlimit(10**5)
def solution(nodeinfo):
    dct= {}
    lst = []
    for i in range(len(nodeinfo)):
        lst.append(nodeinfo[i])
        dct[nodeinfo[i][0]] = i+1
    
    lst.sort(key = lambda x: (-x[1], x[0]))
    lst = collections.deque(lst)
    
    x, _ = lst.popleft()    
    root = Node(x)
    
    while lst:
        node = root
        x, _ =  lst.popleft()
        while node:
            if node.val < x:
                if node.right == None:
                    node.right = Node(x)
                    break
                else:
                    node = node.right
            else:
                if node.left == None:
                    node.left = Node(x)
                    break
                else:
                    node = node.left
       
    answer = []
    
    # preorder
    result = []
    visited = [False for x in range(len(nodeinfo))]    
    def preorder(node):
        if not node:
            return       
        result.append(dct[node.val])
        preorder(node.left)
        preorder(node.right)        
    preorder(root)
    answer.append(result)
    
    # postorder
    result = []
    visited = [False for x in range(len(nodeinfo))]    
    def postorder(node):
        if not node:
            return       
        postorder(node.left)
        postorder(node.right)        
        result.append(dct[node.val])
    postorder(root)
    answer.append(result)     
    
    return answer

뭔가 전형적인 문제?스러웠지만 시간이 오래걸렸다...

트리를 만드는 것에 아직 익숙하지 않다.

자가균형 이진트리는 재귀를 통해 만들수 있단 것을 기억하자.

 

재귀 최대 개수를 늘려주지 않으면 테케를 모두 통과할 수 없다.

프로그래머스에서 이걸 안알려주기때문에 재귀를 쓸 때는 안전하게 늘려주는 게 좋을듯