[CodeKata] 프로그래머스: 10.11(월), 길 찾기 게임

😅 서론

약 1달이 넘게 블로그 포스팅을 하지 않았음을, 오랜만에 블로그 글을 보고 인지하게 되었다.. ㅎㅎ

주된 핑계는, 회사의 코드 리뉴얼 작업에 많은 신경과 작업을 할애함에 따라, 진행하려던 사이드와 포스팅에 신경을 거의 쓰지 못했다.

리뉴얼 작업이 마무리되는 현시점, 여유를 찾음과 동시에 포스팅을 재개하기 위해 주1 알고리즘 부터 시작해보겠다.

---

🥋 Oooth More!! (Level 3) 

 

🧮 풀이

역시, 카카오 문제답게 매우 어려웠다. 특히, 이진트리를 구현함에 있어 클래스 문법이 많이 취약함을 느꼈다.

모범답안을 통해 풀이법을 학습할뿐만 아니라, Javascript 클래스를 숙달할 수 있는 미니프로젝트를 찾아보려고 한다.

 

🖇 리뷰

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

class BinaryTree {
  constructor(root = null) {
    this.root = root;
  }

  add(node) {
    if (this.root === null) {
      this.root = node;
      return;
    }
    if (this.root.x > node.x) {
      if (this.root.left === null) {
        this.root.left = new BinaryTree(node);
        return;
      } else {
        this.root.left.add(node);
      }
    } else {
      if (this.root.right === null) {
        this.root.right = new BinaryTree(node);
        return;
      } else {
        this.root.right.add(node);
      }
    }
  }
  pre(answer) {
    answer.push(this.root.id);
    if (this.root.left !== null) this.root.left.pre(answer);
    if (this.root.right !== null) this.root.right.pre(answer);
  }

  post(answer) {
    if (this.root.left !== null) this.root.left.post(answer);
    if (this.root.right !== null) this.root.right.post(answer);
    answer.push(this.root.id);
  }
}

function solution(nodeinfo) {
  let tree = new BinaryTree();
  nodeinfo = nodeinfo.map((e, id) => {
    return [id + 1, e[0], e[1]];
  });
  nodeinfo.sort((a, b) => a[2] - b[2]);
  let level = nodeinfo[nodeinfo.length - 1][2];
  while (nodeinfo.length) {
    let nodes = nodeinfo.filter(e => level === e[2]);
    nodes.sort((a, b) => b[1] - a[1]);
    nodeinfo = nodeinfo.filter(e => level !== e[2]);
    nodes.forEach(e => {
      let node = new Node(e[0], e[1], e[2]);
      tree.add(node);
    });
    level--;
  }
  let preOrder = [];
  let postOrder = [];
  tree.pre(preOrder);
  tree.post(postOrder);
  return [preOrder, postOrder];
}

1. Node 클래스

• 노드를 만들기 위한 Node 클래스를 정의한다. id는 노드번호, x/y는 노드좌표, left/right는 자식노드 프로퍼티에 해당한다.

 

2. BinaryTree 클래스

• 노드트리를 만들기 위한 BinaryTree 라는 클래스이다. constructor(생성자)는 기본적으로 root 노드 프로퍼티를 가진다.
• < add() 메서드 >는 root가 비어있다면(null) 들어온 노드를 넣어준다.
• 만약 root가 존재한다면, this.root.x 가 현재 node.x 보다 큰지 여부에 따라 root의 left 혹은 right로 보낸다.
• 이 때, 자식노드가 존재하지 않는다면(null) 여기에 새로운 BinaryTree를 그리고, 존재한다면 자식에서 add() 메서드를 재실행한다.
• < pre() 메서드 >, < post() 메서드 > 는 각각의 답을 구하기 위한 메서드이다. answer 배열을 인자로 받으며, 여기에 1) 현재 this.root.id 를 넣어주는 것, 2) 현재 root의 left, right 가 존재하는 경우를 판정하는 것 2가지 역할을 수행한다.
• 단, pre()는 현재 노드를 먼저 push() 한 뒤 left/right 판정을, post()는 left/right 판정을 먼저하여 하위 노드부터 push() 한다.

 

3. solution 함수

• tree 라고 하는 BinaryTree() 클래스의 인스턴스를 선언한다.
• 또한, 인자로 받은 nodeinfo를 [노드번호, x좌표, y좌표] 형태로 map(), 이를 y좌표 기준으로 sort() 정렬한다. (답안은 오름차순 정렬했지만, y값이 클수록 상위노드이므로 내림차순 정렬이 좀 더 직관적이라고 생각!)
• level은 nodeinfo 제일 끝 노드(최상위 노드) 의 y좌표를 의미한다. 이를 기준으로, 남은 nodeinfo 들을 필터링해 나간다.
• while() 문을 실행하며, nodeinfo 가 존재하는 동안 순회한다. 먼저, 현재 level에 해당하는 nodes와 그렇지 않은 nodeinfo로 각각 필터링한다.
• 다음으로, 현재 level의 nodes 각각에 대해 Node() 인스턴스를 형성하고, tree에 노드를 그린다. root에 현재 노드를 넣고, root가 존재한다면 left/right 가 비어있을 땐 자식노드 추가를, 존재한다면 다음 node로의 add() 판정을 진행한다.
• 마지막으로, level을 1씩 감소시키며 while문을 반복한다. (level이 반드시 1간격이 아니므로 y좌표만 필터한 배열을 활용하는 등 방법이 있을 것 같다.)
• 마지막으로, 각각의 정답을 담을 preOrder, postOrder 배열을 만든 뒤, pre(), post() 메서드를 통해 정답을 만들어준다.

---

이진트리의 제작, 탐색 메서드를 만드는 방법에 대해 알게된 문제이다.

Javascript는 다른 컴퓨터 언어처럼 정립된 이진트리 문법이 없어 이렇게 클래스로 대체되어야 하는 것으로 알고있다.

 

카카오의 고난이도 문제, 그리고 최근 풀어봤던 토스 코딩테스트까지 이진트리의 개념은 생각보다 많이 빈출되고 있어 빠른 시일내에 새로운 이진트리 문제를 도전하면서 숙달해나가야겠다고 생각된다!