(프로그래머스 KAKAO JS)길 찾기 게임

https://programmers.co.kr/learn/courses/30/lessons/42892?language=javascript 

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

이진 트리를 구성해 전위 순회와 후위순회를 한 결과를 리턴하는 문제.

Node 라는 클래스를 정의하여 x, y, num, left, right를 가질 수 있도록 하였다.

이를 이용해 주어진 nodeinfo를 순회하여 노드를 만들어준다.

 

node 라는 배열에 Node 클래스를 가진 node가 있으며,

x와 y 좌표를 주어진 조건에 따라 정렬을 한다.

정렬 조건은 y 좌표가 같으면 x 값이 더 작은 값을 앞으로,

그렇지 않다면 y 좌표가 큰 값이 앞으로 정렬되게 한다.

 

정렬된 노드에서 root를 node[0]으로 잡은 후,

이 root를 순회 방식에 맞게 answer에 넣어주면 된다.

class Node {
    constructor(x, y, num){
        this.x = x;
        this.y = y;
        this.num = num;
        this.left = null;
        this.right = null;
    }
}

function solution(nodeinfo) {
    const answer = [[], []];
    const node = [];
    
    const addNode = (parent, child) => {
        if(child.x < parent.x){
            if(parent.left === null){
                parent.left = child;
            } else{
                addNode(parent.left, child);
            }
        } else{
            if(parent.right === null){
                parent.right = child;
            } else{
                addNode(parent.right, child);
            }
        }
    }
    
    const preorder = (node) => {
        if(node === null){
            return;
        }
        
        answer[0].push(node.num);
        preorder(node.left);
        preorder(node.right);
    }
    
    const postorder = (node) => {
        if(node === null){
            return;
        }
        
        postorder(node.left);
        postorder(node.right);
        answer[1].push(node.num);
    }
    
    for(let i = 0; i < nodeinfo.length; i++){
        const [x, y] = nodeinfo[i];
        const num = i + 1;
        const tmpNode = new Node(x, y, num);
        
        node.push(tmpNode);
    }
    
    node.sort((a, b) => {
        if(a.y === b.y){
            return a.x - b.x;
        }
        
        return b.y - a.y;
    });
    
    const root = node[0];
    
    for(let i = 1; i < node.length; i++){
        addNode(root, node[i]);
    }
    
    preorder(root);
    postorder(root);
    
    return answer;
}