[Programmers] [Level3] 길 찾기 게임

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

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

풀이

• 입력으로 [x, y] 좌표 데이터를 원소로 하는 리스트를 받아 조건에 맞게 이진트리를 만든 뒤 전위 순회, 후위 순회했을 때 방문해야할 노드 index리스트를 반환하는 문제

• y값이 level이라 먼저 y값으로 내림차순, x값은 오름차순으로 동시에 정렬하면 순차적으로 node를 추가할 수 있음.

• 전위 순회, 후위 순회는 재귀함수를 사용하면 간단히 구현할 수 있지만 런타임 에러 발생.

  • sys.setrecursionlimit(10**4) 구문을 추가하면 해결되지만, 재귀함수를 쓰지 않는 방법으로 구현

• 전위 순회는 stack을 사용해 구현.

  • 현재 node의 index를 추가
  • 오른쪽, 왼쪽 자식 노드 순으로 stack에 추가(pop할 때 왼쪽 자식 노드를 먼저 방문하기 위함)

• 후위 순회도 stack을 사용해 구현.

  • 후위 순회 결과 값을 거꾸로 봤을 때 현재 노드 방문 -> 오른쪽 자식 노드 방문 -> 왼쪽 자식 노드 방문순
  • 현재 node의 index를 추가
  • 왼쪽, 오른쪽 자식 노드 순으로 stack에 추가(오른쪽 자식 노드 먼저 방문)
  • 거꾸로 된 값을 사용

# 재귀함수를 사용하려면 limit를 늘려야 함. 아니면 런타임 에러 발생
import sys
sys.setrecursionlimit(10**4)

def prefix(idx_lst, node, node_info):
    if node is None:
        return
    idx_lst.append(node_info.index(node.val) + 1)
    prefix(idx_lst, node.left, node_info)
    prefix(idx_lst, node.right, node_info)

def postfix(idx_lst, node, node_info):
    if node is None:
        return
    postfix(idx_lst, node.left, node_info)
    postfix(idx_lst, node.right, node_info)
    idx_lst.append(node_info.index(node.val) + 1)


# 재귀함수 안쓰고 구현한 부분
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None



def prefix_no_recursion(idx_lst, root, node_info):
    stack = [root]
    while stack:
        cur_node = stack.pop()
        idx_lst.append(node_info.index(cur_node.val) + 1)
        if cur_node.right is not None:
            stack.append(cur_node.right)
        if cur_node.left is not None:
            stack.append(cur_node.left)

def postfix_no_recursion(idx_lst, root, node_info):
    stack = [root]
    while stack:
        cur_node = stack.pop()
        idx_lst.append(node_info.index(cur_node.val) + 1)
        if cur_node.left is not None:
            stack.append(cur_node.left)
        if cur_node.right is not None:
            stack.append(cur_node.right)

def solution(node_info):
    answer = []
    n = len(node_info)
    ordered_node = sorted(node_info, key = lambda x:(x[1], -x[0]), reverse=True)
    root = Node(ordered_node[0])
    for node in ordered_node[1:]:
        cur_node = root
        while True:
            if node[0] < cur_node.val[0]:
                if cur_node.left is None:
                    cur_node.left = Node(node)
                    break
                else:
                    cur_node = cur_node.left
            else:
                if cur_node.right is None:
                    cur_node.right = Node(node)
                    break
                else:
                    cur_node = cur_node.right

    prefix_lst = []
    postfix_lst = []
    prefix_no_recursion(prefix_lst, root, node_info)
    postfix_no_recursion(postfix_lst, root, node_info)
    answer.append(prefix_lst)
    postfix_lst = postfix_lst[::-1]
    answer.append(postfix_lst)
    return answer