[2019 카카오 코딩테스트] 길 찾기 게임(파이썬3) / 자체 해설 및 풀이

 

 

지난 '오픈채팅방/후보키/실패율' 문제에 이어

2019 카카오 코딩테스트 '길 찾기 게임' 문제를

파이썬으로 풀어봤다.

 

Tree를 사용한 경험이 거의 없어서 

문제를 보고 트리를 생성할 생각을 하지못해서 한참을 헤맸다.

 

카카오 문제들은 문제를 보고

해결방법을 파악하기가 어려운 것같다.

하지만 방향을 잡고나면 의외로 간단하게 풀린다.

 

 

⬇ 2019/09/02 - [알고리즘/심심풀이 문제풀기] - [2019 카카오 코딩테스트] 실패율(파이썬3) / 자체 해설 및 풀이

[2019 카카오 코딩테스트] 실패율(파이썬3) / 자체 해설 및 풀이

 

 

 

 

 

 

 

 

 

 

코딩테스트 연습 - 길 찾기 게임 | 프로그래머스

 

 

 

 

---

 

자체 해설

 

이 문제는 얼마나 재귀함수를 잘 기획?! 하느냐를 묻는 것 같았다.

트리를 구성하는 것과 트리를 순회하는 부분에서 모두 재귀적 사고를 필요로 했다.

 

* 재귀함수 사용시 필수 확인

파이썬으로 재귀함수를 사용할 경우,

setrecursionlimit(10**6)로 재귀함수(Recursion)의

제한을 풀어야 런타임 에러를 피할 수 있다.

 

Tree 구성하기

1. Tree는 클래스를 선언하여 구성한다.
2. Tree안에 자신의 좌표를 나타내는 data,
   왼쪽 하위 노드(Tree 클래스)를 가리키는 left
   오른쪽 하위 노드(Tree 클래스)를 가리키는 right 로 구성한다.
3. Tree는 초기화 값으로 좌표들의 리스트(ex) [[1,2],[2,3]...] ) 배열을
   받아서 자신을 초기화하도록 init 함수를 만든다.
   
   <__init__ 함수>
   
   1. 초기화 파라미터로 받은 리스트 중에서 y값이 가장 높은 요소가 root가 된다.
   2. root의 x 보다 작은 리스트(root보다 아래, 왼쪽)는 왼쪽 하위 트리를 초기화하는 리스트가 된다.
      left = Tree(  root의 x보다 작은 리스트  ) --> 재귀(Recursion) 함수
   3. root의 x 보다 큰 리스트(root보다 아래, 오른쪽)는 오른쪽 하위 트리를 초기화하는 리스트가된다.
      right = Tree( root의 x보다 큰 리스트 ) --> 재귀(Recursion) 함수

Tree 순회 함수 만들기

1. 트리를 전위/후위 순회하는 함수를 선언한다.
   (일반적인 트리 순회와 크게 다르지 않다.)

 

 

 

 

 

 

 

작성 코드

 

import sys
sys.setrecursionlimit(10**6)

class Tree:
    def __init__(self,dataList):
        self.data=max(dataList,key=lambda x :x[1])
        leftList =list(filter(lambda x :x[0] < self.data[0] , dataList))
        rightList = list(filter(lambda x :x[0] > self.data[0] , dataList))

        if leftList != []:
            self.left=Tree(leftList)
        else :
             self.left=None

        if rightList != []:
            self.right=Tree(rightList)
        else :
             self.right=None

def fix(node,postList,preList):
        postList.append(node.data)
        if node.left is not None:
            fix(node.left,postList,preList)
        
        if node.right is not None:
            fix(node.right,postList,preList)  
        preList.append(node.data)

def solution(nodeinfo):
    answer = []
    root = Tree(nodeinfo)
    postList = []
    preList = []
    fix(root,postList,preList)
    
    answer.append(list(map(lambda x: nodeinfo.index(x)+1 ,postList)))
    answer.append(list(map(lambda x: nodeinfo.index(x)+1 ,preList)))
    return answer

 

 

 

 

카카오 공식 해설 : https://tech.kakao.com/2018/09/21/kakao-blind-recruitment-for2019-round-1/

 

 

---

---

 

 

도움이 되셨다면

로그인이 필요 없는 공감 버튼 꾹 눌러주세요!