프로그래머스 - 길 찾기 게임 (2019 KAKAO BLIND RECRUITMENT) / Level 3

문제 📋

코딩테스트 연습 - 길 찾기 게임

풀이 📝

import sys

sys.setrecursionlimit(10**6)

class Node:
    def __init__(self, key, x):
        self.key = key
        self.x = x
        self.right, self.left = None, None
    
class Tree:
    def __init__(self, root, x):
        self.root = Node(root, x)
        
    def insert(self, key, x):
        cur_node = self.root
        while True:
            if cur_node.x > x: #left down
                if cur_node.left == None: 
                    cur_node.left = Node(key, x)
                    break
                else: cur_node = cur_node.left
            elif cur_node.x < x: #right down
                if cur_node.right==None: 
                    cur_node.right = Node(key, x)
                    break
                else: cur_node = cur_node.right

    def preorder(self):
        res = []
        
        def order(node):
            nonlocal res
            res.append(node.key)
            
            if node.left != None: 
                order(node.left)
                
            if node.right != None: 
                order(node.right)
                
        order(self.root)
        return res
        
    def postorder(self):
        res = []
        
        def order(node):
            nonlocal res
            if node.left != None: 
                order(node.left)
                
            if node.right != None: 
                order(node.right)
                
            res.append(node.key)
            
        order(self.root)
        return res
        
def solution(nodeinfo):
    answer = []
    
    for i in range(len(nodeinfo)): 
        nodeinfo[i] = [i+1] + nodeinfo[i]
        
    nodeinfo.sort(key=lambda x : -x[2])
    
    tree = Tree(nodeinfo[0][0], nodeinfo[0][1])
    
    for i in nodeinfo[1:]: 
        tree.insert(i[0], i[1])
        
    answer.append(tree.preorder())
    answer.append(tree.postorder())
    
    return answer

상당히 어렵게 느껴졌던 문제였고 풀이에 실패하여 다른 사람의 코드를 분석해보았다.

일단 Tree traversal 같은 경우엔 Tree 구조가 다 구현되어지면 재귀로 비교적 쉽게 구현 가능했지만

Tree와 Node를 주어진 조건에 따라 구현하는게 헷갈리는 부분이 많았다.
그래도 node 정보들을 y좌표 값에 따라 정렬함에 따라 x좌표 값만 비교하여 하나씩 insert하여 tree를 구성할 수 있었다.

어떻게 보면 node와 tree를 구성하는 것은 전공 수업때 많이 해봤던 기본적인 부분인데
오래만에 그리고 짧은 시간내에 하려니 어려운 부분이 있었다. 좀 더 알고리즘, 자료구조의 기본적인 부분을 갈고 닦아야 겠다.