[프로그래머스][KAKAO_BLIND][2019] 길 찾기 게임

프로그래머스 코딩테스트 고득점 Kit의 문제입니다.

https://programmers.co.kr/learn/challenges?tab=algorithm_practice_kit

코딩테스트 연습

 

문제

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

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

 

내가 작성한 코드

from collections import defaultdict, deque
import sys
sys.setrecursionlimit(10000)

def set_idx(nodeinfo):
    idx = defaultdict(defaultdict)
    for i, t in enumerate(nodeinfo):
        x, y = t
        idx[x][y] = i+1
    return idx

def set_x_in_y(y_max_sorted):
    dic = defaultdict(deque)
    for x, y in y_max_sorted:
        dic[y].append(x)
    return dic

def get_idx(x, y, idx):
    return idx[x][y]

def pre(dic, pre_ans, post_ans, x, mx, layers, idx):
    y = layers[-1]
    pre_ans.append(get_idx(x,y,idx))
    dic[y].popleft()

    layers = layers[:-1]
    if layers:
        next_y = layers[-1]
        next_xs = dic[next_y]
        if len(next_xs) and next_xs[0] < x:
            next_x = next_xs[0]
            pre(dic, pre_ans, post_ans, next_x, x, layers, idx)
        if len(next_xs) and x < next_xs[0] < mx:
            next_x = next_xs[0]
            pre(dic, pre_ans, post_ans, next_x, mx, layers, idx)
    post_ans.append(get_idx(x,y,idx))

def solution(nodeinfo):
    y_max_sorted = sorted(nodeinfo, key=lambda x: (-x[1], x[0]))
    dic = set_x_in_y(y_max_sorted)
    idx = set_idx(nodeinfo)
    layers = sorted(dic)

    pre_ans = []
    post_ans = []
    pre(dic, pre_ans, post_ans, y_max_sorted[0][0], sys.maxsize, layers, idx)

    return [pre_ans, post_ans]

if __name__ == '__main__':
    nodeinfo = [[5, 1], [3, 0], [7, 0]]
    print(solution(nodeinfo))

• 이진 트리
  • y좌표 기준
    - 가장 큰 값이 root
    - y좌표가 0 ~ max 까지 모두 존재하지 않음 ex. 1, 2, 4, 5, 6
    - y값이 같으면 같은 계층의 노드
  • x좌표 기준
    - x값이 작으면 left / x값이 크면 right
    - x는 자신의 부모노드보다 작아야하므로, x의 right는 x < right < root
• 순회
  • 전위순회
    - root -> left -> right
    - 재귀시 시작하자마자 해당 노드의 인덱스를 결과에 삽입
  • 후위순회
    - left -> right -> root
    - 전위순회 과정에서 right가 끝난 후 결과에 삽입
    - left를 먼저 탐색, left가 없고 right가 있으면 right의 left를 탐색, 이 후에도 right까지 없으면 삽입
    - 즉, left가 우선인 상황에서 right까지 모두 탐색 후 root가 삽입됨

 

다른 사람이 작성한 코드

None

 

기억해야할 것

• recursion 횟수 제한
  
  • 정답인 것 같은데 런타임 에러가 계속 발생해서 질문하기에 들어가봤다
  • recursion limit 이야기가 있었다
  • sys.setrecursionlimit을 10000으로 설정해주니 통과했다
• recursionlimit의 default값은?
  • 프로그래머스는 현재 python 3.8.5 (default가 몇인지 모르겠다)
  • python 3.9.1에서는 sys.getrecursionlimit()의 결과값이 1000 (3.8.5도 같은 1000이라고 생각하면)
  • "트리의 깊이가 1,000 이하인 경우만 입력으로 주어진다"라는 조건이 문제에 있다
  • 이를 보고 recursion limit을 떠올렸어야했는데 그러지 못했다
    - 높이가 1000이하로, 다른 함수에 대한 stack의 깊이를 생각하면 여유가 필요하다
    - 1001, 1002는 여전히 런타임 에러이며, 1010은 통과된다