[프로그래머스 lev3/JS] 길 찾기 게임

문제 출처

프로그래머스 lev3 - 길 찾기 게임

나의 풀이 (성공)

트리를 구현하고 전위순회, 후위순회만 구현하면 끝나는 문제.

y가 레벨을 의미하므로 y가 가장 높은 노드부터 tree에 삽입을 하면 되는데, 단순히 정렬을 하려니 index가 꼬여서 먼저 list 객체에 인덱스와 노드를 맵핑해두고 꺼내썼다.

class Node {
  x;y;ValueIdx;
  left;right;
  constructor(x, y, ValueIdx){
    this.x = x
    this.y = y 
    this.ValueIdx = ValueIdx
    this.left = null 
    this.right = null 
  }
}
class BST {
  root = null;
  
  // 노드 삽입 
  _insertNode = (node, x, y, ValueIdx) => {
    if(node === null) node = new Node(x, y, ValueIdx)
    else if(y < node.y && x < node.x){
      node.left = this._insertNode(node.left, x, y, ValueIdx)
    }
    else if(y < node.y && x > node.x){
      node.right = this._insertNode(node.right, x, y, ValueIdx)
    }
    return node 
  }
  insert = (x, y, ValueIdx) => {
    this.root = this._insertNode(this.root, x, y, ValueIdx)
  }
  // 전위 순회 
  _preorder = (node, callback) => {
    if(node === null) return 

    callback(node)
    this._preorder(node.left, callback)
    this._preorder(node.right, callback)
  }
  preorder = (callback) => {
    this._preorder(this.root, callback)
  }
  // 후위 순회 
  _postorder = (node, callback) => {
    if(node === null) return 

    this._postorder(node.left, callback)
    this._postorder(node.right, callback)
    callback(node)
  }
  postorder = (callback) => {
    this._postorder(this.root, callback)
  }
}

function solution(nodeinfo) {
  let tree = new BST()
  let answer = [[], []]
  let list = {} 

  nodeinfo.map((v, i) => {
    list[v] = i+1
  })  
  
  nodeinfo
    .sort((a,b) => b[1] - a[1])
    .map((v, i) => {
      tree.insert(v[0], v[1], list[v])
    })
  
  const pre = (node) => answer[0].push(node.ValueIdx)
  const post = (node) => answer[1].push(node.ValueIdx)
  
  tree.preorder(pre)
  tree.postorder(post)

  return answer 
}

console.log(
  solution([
    [5, 3],
    [11, 5],
    [13, 3],
    [3, 5],
    [6, 1],
    [1, 3],
    [8, 6],
    [7, 2],
    [2, 2],
  ])
); // [[7, 4, 6, 9, 1, 8, 5, 2, 3], [9, 6, 5, 8, 1, 4, 3, 2, 7]]

다른 풀이 1

function solution(nodelist) {
    let rootNode
    let preorder = []
    let postorder = []

    const Node = function (x, y, id) {
        this.x = x
        this.y = y
        this.id = id
        this.left = null
        this.right = null
    }

    const insertNode = (x, y, id) => {
        if (!rootNode) {
            rootNode = new Node(x, y, id)
        } else {
            _insertNode(rootNode, x, y, id)
        }
    }

    const _insertNode = (node, x, y, id) => {
        const side = x < node.x ? 'left' : 'right'

        if (node[side] === null) {
            node[side] = new Node(x, y, id)
        } else {
            _insertNode(node[side], x, y, id)
        }
    }

    const _preorder = node => {
        preorder.push(node.id)
        if (node.left) _preorder(node.left)
        if (node.right) _preorder(node.right)
    }

    const _postorder = node => {
        if (node.left) _postorder(node.left)
        if (node.right) _postorder(node.right)
        postorder.push(node.id)
    }

    const nodes = nodelist.map(([x, y], idx) => [x, y, idx+1])
    nodes.sort(([, ya], [, yb]) => yb - ya)
    nodes.forEach(([x, y, id]) => insertNode(x, y, id))

    _preorder(rootNode)
    _postorder(rootNode)

    return [preorder, postorder]
}

다른 풀이 2

const makeTree = (root, nodes) =>{
    if(nodes.length == 0)return; 
    const left = nodes.filter(e => root.x > e.x)
    const right = nodes.filter(e => root.x < e.x)
    if(left){
        root.left = left[0];
        makeTree(left[0], left)
    }
    if(right){
        root.right = right[0];
        makeTree(right[0], right)
    } 
    return root; 
} 
let preOrder = []; 
let postOrder = []; 
const getPre = tree =>{ 
    preOrder.push(tree.idx) 
    if(tree.left)getPre(tree.left)
    if(tree.right)getPre(tree.right);
}
const getPost = tree =>{  
    if(tree.left)getPost(tree.left)
    if(tree.right)getPost(tree.right);
    postOrder.push(tree.idx) 
}
function solution(nodeinfo) { 
    nodeinfo = nodeinfo.map((e, idx) => {
        return {"idx" : idx + 1, "x": e[0], "y": e[1]}
    })
    nodeinfo.sort((a, b)=>{
        if(a.y == b.y){
            return a.x - b.x;
        }
        return (a.y - b.y) * -1
    })
    const tree = makeTree(nodeinfo[0], nodeinfo);
    getPre(tree)
    getPost(tree) 
    const answer = [preOrder, postOrder] 
    return answer;
}