[프로그래머스] 길 찾기 게임 (2019 KAKAO BLIND RECRUITMENT)

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

프로그래머스

 

x좌표의 상대적인 위치를 이용하여 이진트리의 구성을 파악하고 전위/후위순위 결과를 출력하는 문제

처음에는 직접 간선을 연결하고 그래프 순회를 해야하나 생각했는데, '이진트리' 라는 특성상 계속해서 좌/우 구분이 나눠지는 관계를 이용해서 현재 루트 노드가 커버하는 범위를 계속 좁혀나가면서 특정 x좌표의 노드가 현재 노드의 왼쪽/오른쪽 자식인지 판단하도록 하였다.

현재 노드의 자식노드인지 판별하는 것은 현재 노드가 커버하는 범위 안에 포함되어 있는지 체크하는 것으로 판단하였다.

 

import sys
sys.setrecursionlimit(2000)
def solution(nodeinfo):
    info = dict()
    number = 1
    for x, y in nodeinfo:
        if y in info:
            info[y].append((x, number))
            number += 1
        else:
            info[y] = [(x, number)]
            number += 1
    
    for y in info:
        info[y].sort()
    
    y_list = sorted(info.keys(), reverse=True)
    preorder_list = []
    postorder_list = []
    def order(y_idx, now_x, now_number, now_range):
        preorder_list.append(now_number)
        if y_idx == len(y_list)-1:
            postorder_list.append(now_number)
            return
        
        next_y = y_list[y_idx+1]
        for next_x, next_number in info[next_y]:
            if now_range[0] <= next_x <= now_range[1]:
                if next_x < now_x:
                    order(y_idx+1, next_x, next_number, (now_range[0], now_x))
                else:
                    order(y_idx+1, next_x, next_number, (now_x, now_range[1]))
        postorder_list.append(now_number)
    
    start_x, start_number = info[y_list[0]][0]
    order(0, start_x, start_number, (0, 100000))
        
    answer = [preorder_list, postorder_list]
    return answer

 

파이참에서는 재귀 깊이 제한이 2000이라 넉넉할 줄 알았는데, 프로그래머스에서는 재귀깊이가 1000이었다.

문제 조건상 최대 재귀깊이는 1000이었고, solution 함수의 호출까지 포함하면 재귀 깊이가 최대 1001이 될 수 있어서 일부 테케에서 재귀 깊이 초과에 따른 런타임에러가 발생했다. (이유는 알려주지 않았지만 재귀 설정 이후 맞았다)

재귀를 사용하는 문제의 경우 습관적으로 재귀 깊이 제한을 늘려주도록 해야겠다.