알고리즘 (PS)/Programmers

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

2025. 3. 20. 23:03
반응형

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
'알고리즘 (PS)/Programmers' 카테고리의 다른 글
  • [프로그래머스] 이중우선순위큐
  • [프로그래머스] 시험장 나누기 (2021 카카오 채용연계형 인턴십)
  • [프로그래머스] 도넛과 막대 그래프 (2024 KAKAO WINTER INTERNSHIP)
  • [프로그래머스/python3] 다트 게임 (2018 KAKAO BLIND RECRUITMENT [1차])
에버듀
에버듀
개발은 좋은데 뭘로 개발할까
에버듀
Blog. 에버듀
에버듀
전체
오늘
어제
  • 분류 전체보기 (602) N
    • 개인 프로젝트 (43)
      • [2020] 카카오톡 봇 (9)
      • [2021] 코드악보 공유APP (22)
      • [2022] 유튜브 뮤직 클론코딩 (9)
      • 간단한 프로젝트 (3)
    • 팀 프로젝트 (22)
      • [2020] 인공지능 숫자야구 (4)
      • [2022] OSAM 온라인 해커톤 (10)
      • [2024] GDSC 프로젝트 트랙 (6)
      • [2025] 큰소리 웹 페이지 (2)
    • 알고리즘 (PS) (107)
      • BOJ (101)
      • Programmers (5)
      • 알고리즘 이모저모 (1)
    • CS (326) N
      • 자료구조 (19)
      • 어셈블리 (41)
      • 멀티미디어응용수학 (7)
      • 컴퓨터 구조 (29)
      • 알고리즘 분석 (4)
      • 컴퓨터 네트워크 (38)
      • 프로그래밍언어론 (15)
      • HCI 윈도우즈프로그래밍 (26)
      • 기초데이터베이스 (29)
      • 운영체제 (23)
      • 오토마타 (24)
      • 문제해결기법 (11)
      • 블록체인 (22)
      • 소프트웨어공학 (21) N
      • 기계학습심화 (12)
      • 컴퓨터그래픽스와 메타버스 (5) N
    • 자기계발 (36)
      • 동아리 (7)
      • 자격증 (2)
      • 코딩테스트, 대회 (8)
      • 생각 정리 (18)
      • 머니 스터디 (1)
    • WEB(BE) (5)
      • express.js (1)
      • flask (0)
      • Spring & Spring Boot (4)
    • WEB(FE) (2)
      • html, css, js (1)
      • React.js (1)
    • Tool & Language (6)
      • Edit Plus (1)
      • Git (1)
      • Python3 (2)
      • Java (2)
    • Infra (12)
      • AWS (1)
      • Oracle Cloud (8)
      • Firebase (2)
      • Network (1)
    • Android (18)
      • Java (6)
      • Flutter (12)
    • Window (2)
      • Visual Studio 없이 WPF (1)
      • MFC (1)
    • 독서 (14)
      • Inside Javascript (7)
      • Database Internals (6)
      • 한 글 후기 (1)
    • 인턴 (8)
      • 델파이 (7)
      • Oracle (1)

인기 글

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.1.4
에버듀
[프로그래머스] 길 찾기 게임 (2019 KAKAO BLIND RECRUITMENT)
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.