2018 카카오 블라인드 코딩 테스트 1차 길 찾기 게임

root의 y값은 가장 크다. 이후의 root의 왼쪽, 오른쪽 자식은 차례대로 y값이 감소한다. 자식 삽입은 자식의 x값이 root의 x보다 큰지 작은지로 판단하면 된다.

 

테스트 케이스 6, 7번 런타임 에러가 나는 경우가 있는데 python에선 stack overflow를 방지하기 위해 재귀 횟수에 제한을 둔다. 횟수 제한 확인은 파이썬 콘솔 상에서 아래 코드를 입력하면 된다. 제한은 1000번이다.

import sys

sys.getrecursionlimit()

 

재귀 제한을 변경하는 방법은 아래와 같다.

import sys
sys.setrecursionlimit(10**4)

이걸 코드 상단에 작성해주면 이 문제에 대한 테스트 케이스를 커버할 수 있다.

 

아래 작성한 find() 메서드는 사용되지 않는다.

import sys
sys.setrecursionlimit(10**6)

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


class BT:
    def __init__(self):
        self.root = None

    def insert(self, data):
        self.root = self._insert(self.root, data)
        return self.root is not None

    def _insert(self, node, val):
        if node is None:
            node = Node(val)
        else:
            if val[0] < node.data[0]:
                node.left = self._insert(node.left, val)
            else:
                node.right = self._insert(node.right, val)
        return node

    def find(self, key):  # x 값으로 찾기
        return self._find(self.root, key)

    def _find(self, node, key):
        if node is None or node.data == key:
            return node is not None
        elif key < node.data:
            return self._find(node.left, key)
        else:
            return self._find(node.right, key)

    def pre_order(self):
        pre_list = []

        def _pre_order(root):
            if root is None:
                return
            else:
                pre_list.append(root.data[2])
                _pre_order(root.left)
                _pre_order(root.right)
        _pre_order(self.root)
        return pre_list

    def post_order(self):
        post_list = []

        def _post_order(root):
            if root is None:
                return
            else:
                _post_order(root.left)
                _post_order(root.right)
                post_list.append(root.data[2])
        _post_order(self.root)
        return post_list


def solution(nodeinfo):
    for i, v in enumerate(nodeinfo):  # index+1 넣기
        v.append(i+1)
    nodeinfo = sorted(nodeinfo, key=lambda k: (-k[1],k[0]))  # level 큰거 순으로 정렬, x가 작은 순서대로 정렬
    bt = BT()
    for node in nodeinfo:
        bt.insert(node)
    return [bt.pre_order(), bt.post_order()]


print(solution([[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]]))

 

 

출처 https://www.welcomekakao.com/learn/courses/30/lessons/42892

코딩테스트 연습 - 길 찾기 게임 | 프로그래머스

python recursion limit https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it

What is the maximum recursion depth in Python, and how to increase it?