2019 KAKAO BLIND RECRUITMENT- 길 찾기 게임, 파이썬

1. 문제

- 2차원 배열로 좌표가 주어지면 주어진 조건에 따라 전위순회, 후위순회 배열을 리턴하면 된다. 

 

2. 풀이

- 이진트리에서 전위 순회(preorder), 후위 순회(postorder)에 대한 내용을 알고 있으면 크게 어렵지 않은 문제이다. 

- 트리 자료구조를 구현하여 풀 수도 있지만 그냥 풀릴것 같아서 풀어봤다. 

- 다만 테스트 6번, 7번에서 런타임 에러가 났는데 찾아보니 파이썬 재귀함수 횟수 제한에 걸려서 그렇다고 한다. 

- 재귀 제한이 기본 1000으로 걸려있다고 한다. 

- 재귀 제한 안에 푸는 것도 문제에서 요구하는 것인가 잠깐 생각해봤지만 재귀 제한을 1005로 늘렸을 때 테스트를 통과하는 것으로 봐서는 문제 설계의 오류가 아닌가 의심해본다(희망사항)

- 솔직히 sys.setrecursionlimit(limit_number) 이걸 누가 알고있나 싶어서... ㅠㅠ 실제 테스트였다면 당황했을듯

 

3. 코드

import sys
sys.setrecursionlimit(1005)

def solution(nodeinfo):
    for i in range(len(nodeinfo)):
        nodeinfo[i].append(i+1)
    nodeinfo.sort(key = lambda x :(-x[1], x[0]))
    pre = []
    post = []
    return_order(nodeinfo, pre, post)
    return [[x[2] for x in pre], [x[2] for x in post]]

def return_order(arr, pre, post) :
    if arr :
        root = arr[0]
        pre.append(root)
        left = []
        for x in arr[1:] :
            if x[0] < root[0] :
                left.append(x)
        return_order(left, pre, post)
        right = []
        for y in arr[1:] :
            if y[0] > root[0] :
                right.append(y)
        return_order(right, pre, post)
        post.append(root)