프로그래머스 [Lv. 3] 길 찾기 게임 {언어 : JavaScript} [다시 풀어 보기]

문제 링크

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

프로그래머스

정답 코드

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

    insert(node) {
        if (node.x < this.x) {
            if (this.left === null) {
                this.left = node;
            } else {
                this.left.insert(node);
            }
        } else {
            if (this.right === null) {
                this.right = node;
            } else {
                this.right.insert(node);
            }
        }
    }
}

function preorder(node, result) {
    if (node !== null) {
        result.push(node.number);
        preorder(node.left, result);
        preorder(node.right, result);
    }
}

function postorder(node, result) {
    if (node !== null) {
        postorder(node.left, result);
        postorder(node.right, result);
        result.push(node.number);
    }
}

function solution(nodeinfo) {
    const nodes = nodeinfo.map(([x, y], index) => ({
        number: index + 1,
        x: x,
        y: y
    }));

    nodes.sort((a, b) => b.y - a.y || a.x - b.x);
    rootNode = nodes[0];
    const root = new Node(rootNode.number, rootNode.x, rootNode.y);

    for (let i = 1; i < nodes.length; i++) {
        iNode = nodes[i];
        root.insert(new Node(iNode.number, iNode.x, iNode.y));
    }
    const preorderResult = [];
    const postorderResult = [];

    preorder(root, preorderResult);
    postorder(root, postorderResult);

    return [preorderResult, postorderResult];
}

풀이 방법

1. 클래스를 만들어서 node번호, x, y, left, right를 만들었다.
2. nodes라는 배열을 만드는데 배열을 Object형태로 넣어준다.
3. nodes를 정렬 할 때 y값이 큰 것이 맨 위로 올라가고 왼쪽부터 나오게 정렬한다.
   1. nodes의 요소가 class Node로 되어있기 때문에 b.y - a.y (y가 큰 값부터 나열) || a.x - b.x (x가 작은 값부터 나열)
4. root를 만들어서 아래와 같은 형태로 저장한다. (Node의 insert함수를 사용)
5. 이후 중위 순회와 후위 순회를 해서 값을 return하면 끝!

Node {
  number: 7,
  x: 8,
  y: 6,
  left: Node {
    number: 4,
    x: 3,
    y: 5,
    left: Node { number: 6, x: 1, y: 3, left: null, right: [Node] },
    right: Node { number: 1, x: 5, y: 3, left: null, right: [Node] }
  },
  right: Node {
    number: 2,
    x: 11,
    y: 5,
    left: null,
    right: Node { number: 3, x: 13, y: 3, left: null, right: null }
  }
}

느낀점

• 이진트리 만드는 방법을 다시 한번 배울 수 있었다.