반응형
https://school.programmers.co.kr/learn/courses/30/lessons/42892
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
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이 될 수 있어서 일부 테케에서 재귀 깊이 초과에 따른 런타임에러가 발생했다. (이유는 알려주지 않았지만 재귀 설정 이후 맞았다)
재귀를 사용하는 문제의 경우 습관적으로 재귀 깊이 제한을 늘려주도록 해야겠다.
반응형
'알고리즘 (PS) > Programmers' 카테고리의 다른 글
[프로그래머스] 이중우선순위큐 (0) | 2025.03.22 |
---|---|
[프로그래머스] 시험장 나누기 (2021 카카오 채용연계형 인턴십) (0) | 2025.03.21 |
[프로그래머스] 도넛과 막대 그래프 (2024 KAKAO WINTER INTERNSHIP) (0) | 2024.11.22 |
[프로그래머스/python3] 다트 게임 (2018 KAKAO BLIND RECRUITMENT [1차]) (0) | 2022.11.13 |