길 찾기 게임

길 찾기 게임
2019 KAKAO BLIND RECRUITMENT 
1482명 완료

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

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

이진트리를 만들어 본 적 있다면, 어렵지 않을 것 같습니다. 

https://comdoc.tistory.com/entry/20-%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%AC%EC%99%80-%EC%9D%B4%EC%A7%84-%EA%B2%80%EC%83%89-%ED%8A%B8%EB%A6%AC2-%ED%83%90%EC%83%89-%EC%B5%9C%EB%8C%80-%EC%B5%9C%EC%86%8C?category=800088

재귀의 한계를 조절해야 합니다.   

class Node:
    def __init__(self, x, y, index):
        self.x = x
        self.y = y
        self.index = index
        self.left = None
        self.right = None


def preorder(node, pre_list):
    if node is not None:
        pre_list.append(node.index)
        preorder(node.left, pre_list)
        preorder(node.right, pre_list)


def postorder(node, post_list):
    if node is not None:
        postorder(node.left, post_list)
        postorder(node.right, post_list)
        post_list.append(node.index)


def solution(node_info):
    import sys
    sys.setrecursionlimit(10 ** 6)
    for idx, (x, y) in enumerate(node_info):
        node_info[idx] = (x, y, idx + 1)
    node_info.sort(key=lambda a: a[1], reverse=True)
    root = None
    for (x, y, index) in node_info:
        node = Node(x, y, index)
        if root is None:
            root = node
            continue
        current = root
        while True:
            parent = current
            if x < current.x:
                current = current.left
                if current is None:
                    parent.left = node
                    break
            else:
                current = current.right
                if current is None:
                    parent.right = node
                    break
    pre_list = []
    post_list = []
    preorder(root, pre_list)
    postorder(root, post_list)
    return [pre_list, post_list]

개인적으로는 위 코드가 직관적이고 편합니다만,
재귀는 리턴으로 정리하는 게 깔끔한 느낌도 있습니다. 

class Node:
    def __init__(self, x, y, index):
        self.x = x
        self.y = y
        self.index = index
        self.left = None
        self.right = None


def preorder(node, pre_list):
    if node is not None:
        pre_list.append(node.index)
        preorder(node.left, pre_list)
        preorder(node.right, pre_list)
    return pre_list


def postorder(node, post_list):
    if node is not None:
        postorder(node.left, post_list)
        postorder(node.right, post_list)
        post_list.append(node.index)
    return post_list


def solution(node_info):
    import sys
    sys.setrecursionlimit(10 ** 6)
    for idx, (x, y) in enumerate(node_info):
        node_info[idx] = (x, y, idx + 1)
    node_info.sort(key=lambda a: a[1], reverse=True)
    root = None
    for (x, y, index) in node_info:
        node = Node(x, y, index)
        if root is None:
            root = node
            continue
        current = root
        while True:
            parent = current
            if x < current.x:
                current = current.left
                if current is None:
                    parent.left = node
                    break
            else:
                current = current.right
                if current is None:
                    parent.right = node
                    break
    return [preorder(root, []), postorder(root, [])]

테스트 1 〉	통과 (0.03ms, 9.61MB)
테스트 2 〉	통과 (0.06ms, 9.55MB)
테스트 3 〉	통과 (0.02ms, 9.35MB)
테스트 4 〉	통과 (0.02ms, 9.62MB)
테스트 5 〉	통과 (0.02ms, 9.52MB)
테스트 6 〉	통과 (45.07ms, 10.5MB)
테스트 7 〉	통과 (42.25ms, 10.5MB)
테스트 8 〉	통과 (31.52ms, 11.1MB)
테스트 9 〉	통과 (149.62ms, 13.5MB)
테스트 10 〉	통과 (10.15ms, 10.1MB)
테스트 11 〉	통과 (127.78ms, 13.5MB)
테스트 12 〉	통과 (145.96ms, 13.5MB)
테스트 13 〉	통과 (0.62ms, 9.62MB)
테스트 14 〉	통과 (4.36ms, 9.86MB)
테스트 15 〉	통과 (13.01ms, 11.5MB)
테스트 16 〉	통과 (28.41ms, 13.5MB)
테스트 17 〉	통과 (3.05ms, 9.89MB)
테스트 18 〉	통과 (31.87ms, 13.4MB)
테스트 19 〉	통과 (5.55ms, 10.3MB)
테스트 20 〉	통과 (12.29ms, 11.2MB)
테스트 21 〉	통과 (18.92ms, 11.8MB)
테스트 22 〉	통과 (31.26ms, 13.5MB)
테스트 23 〉	통과 (32.09ms, 13.4MB)
테스트 24 〉	통과 (0.03ms, 9.58MB)
테스트 25 〉	통과 (0.03ms, 9.7MB)
테스트 26 〉	통과 (69.51ms, 11MB)
테스트 27 〉	통과 (0.03ms, 9.56MB)
테스트 28 〉	통과 (0.06ms, 9.61MB)
테스트 29 〉	통과 (0.01ms, 9.57MB)