프로그래머스 레벨3 - 카카오 2019 길 찾기 게임

문제주소

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

내 풀이

# ✨ 파이썬 기본 재귀 limit이 1000이라 늘려주어야 한다! 
import sys
sys.setrecursionlimit(10**6)

class Node:
    def __init__(self, info):
        self.data = info[0]
        self.value = info[1]
        self.left, self.right = None, None

class NodeTree:
    def __init__(self, parent):
        self.parent = parent
    def insert(self, info):
        self.cur_node = self.parent
        while True:
            if info[0][0] < self.cur_node.data[0]:
                if self.cur_node.left != None:
                    self.cur_node = self.cur_node.left
                else:
                    self.cur_node.left = Node(info)
                    break
            else:
                if self.cur_node.right != None:
                    self.cur_node = self.cur_node.right
                else:
                    self.cur_node.right = Node(info)
                    break                 

def solution(nodeinfo):
    answer = [[],[]]
    for i in range(len(nodeinfo)):
        nodeinfo[i] = (nodeinfo[i],i+1)
    nodeinfo.sort(key=lambda x : -x[0][1])
    head = Node(nodeinfo[0])
    tree = NodeTree(head)
    for i in range(1, len(nodeinfo)):
        tree.insert(nodeinfo[i])
    answer[0] = preorder(head, [])
    answer[1] = postorder(head,[])
    return answer

def preorder(node, answer):
    if node == None:
        return answer
    answer.append(node.value)
    preorder(node.left, answer)
    preorder(node.right, answer)
    return answer

def postorder(node, answer):
    if node == None:
        return answer
    postorder(node.left, answer)
    postorder(node.right, answer)
    answer.append(node.value)
    return answer

파이썬에서 재귀로 풀 땐 limit 확인하고 늘려주어야 한다!!!

다른 사람 풀이

거의 트리를 만들어서 푼 사람들이 대다수였던 것 같다. 

정리

이진트리 구현은 처음해본다. 파이썬에서는 이진트리 자료구조를 사용하는 heap 같은 자료구조는 지원해주지만 이진트리 자체는 지원해주진 않아서 구현해야 한다고 한다. 인터넷에서 이진트리 구현을 찾아보면서 작성했다. 전위순회, 후위순회 등의 개념도 처음 알게 되었다. 파이썬에서 class를 처음 사용해보는데 저렇게 쓰면 되는구나 느꼈다. __init__ 이렇게 언더바가 2개 붙은 메소드명은 초기화를 담당하거나 약간 특별한 역할을 해주는 메소드들이다. 뭔가 이진트리에 대한 개념의 이해가 있으면 특별한 제약조건 없이 풀 수 있는 문제라고 느껴졌다.

카카오 문제들이 엄청 조건이 까다롭게 걸리는 문제들이 많아서 힘들었는데, 중간에 이런 문제도 나오는구나 싶었다. 역시 자료구조 공부를 해야한다!!😅 이렇게 트리라는 자료구조를 공부할 수 있어 다행이다!