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

[프로그래머스][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은 통과된다

from http://pythaac.tistory.com/224 by ccl(A) rewrite - 2021-09-02 21:00:09