[프로그래머스 lev3/JS] 표현 가능한 이진트리

문제 출처

프로그래머스 lev3 - 표현 가능한 이진트리

나의 풀이

포화이진트리이므로, 항상 부모자식은 3개의 노드 관계를 갖는다.
이때 중위선회를 가정하면 부모노드가 0이면 안 된다.
즉, [왼쪽자식, 부모, 오른쪽 자식] 일 때

• 가능한 케이스 : 011 111 110 010
• 불가능한 케이스 : 101 001 100

이때 처음에는 3개씩 자르려 했으나 그럴 수 없다.
그래서 가운데 있는 부모 노드만 찾아서 판단해주는 식으로 했다.

st 함수는 포화이진트리를 완성하는 건데,
cnt는 트리의 높이가 되고
sum은 노드의 개수가 된다.
이진트리 개념을 자세히는 몰라서 while 문을 사용했다.

check 함수에서는 부모 노드와 그 외 트리를 왼쪽과 오른쪽으로 나눠 재귀를 진행한다. 부모 노드가 0이고 자식에 하나라도 노드가 있으면 완성할 수 없는 트리라고 판단한다.

function st(num) {
  let cnt = 0;
  let sum = 0;
  let binNum = num.toString(2);
  let len = binNum.length;
  while (sum < len) {
    sum += 2 ** cnt;
    cnt++;
  }

  return "0".repeat(sum - len) + binNum;
}

function check(tree, parent) {
  if (parent === "0" && tree.indexOf("1") !== -1) return false;
  if (tree.length === 0) return true;

  const subParent = parseInt(tree.length / 2);
  return (
    check(tree.slice(0, subParent), tree[subParent]) &&
    check(tree.slice(subParent + 1), tree[subParent])
  );
}

function solution(numbers) {
  const answer = [];
  for (let i = 0; i < numbers.length; i++) {
    const bt = st(numbers[i]);
    const s = bt[parseInt(bt.length / 2)];
    // 가능 : 011 111 110 010
    // 불가능 : 101 001 100
    // 무조건 3개로 자르는 게 아니다.
    // 길이는 홀수가 나오는데, 2레벨이면 == 1 1 1; 3레벨이면 == 111 1 111; 4레벨이면 == 111 1 111 1 111 1 111
    check(bt, s) ? answer.push(1) : answer.push(0);
  }
  return answer;
}

다른 풀이

개념을 알았다면 더 빠르게 풀 수 있었을 것 같다.

높이가 h인 이진 트리의 노드 개수(n) : 2**n - 1
n개의 노드를 가진 이진 트리의 높이(h) : Math.log2(n + 1)

예를 들어 이진수가 111이면 앞에 0들이 생략된 것이므로 노드 개수만큼 추가할 수 있다.

function checkTree(tree, parent) {
  if (parent === '0' && tree.indexOf('1') !== -1) return false;
  if (tree.length === 0) return true;

  const prevParent = parseInt(tree.length / 2);
  return (
    checkTree(tree.slice(0, prevParent), tree[prevParent]) &&
    checkTree(tree.slice(prevParent + 1), tree[prevParent])
  );
}

function makeCompleteBinaryTree(num) {
  const binNum = num.toString(2);
  const lengthOfbinNum = binNum.length;
  const treeHeight = Math.ceil(Math.log2(lengthOfbinNum + 1));
  const numberOfNodes = 2 ** treeHeight - 1;

  return '0'.repeat(numberOfNodes - lengthOfbinNum) + binNum;
}

function solution(numbers) {
  const answer = numbers.map(num => {
    const completeBinaryTree = makeCompleteBinaryTree(num);
    const root = completeBinaryTree[parseInt(completeBinaryTree.length / 2)];

    return checkTree(completeBinaryTree, root) ? 1 : 0;
  });

  return answer;
}

개념정리

이진탐색을 사용하면 시간 복잡도를 O(n)에서 O(logN)으로 줄일 수 있다.

초기값 설정 : left = 0, right = arr.length -1
mid값 설정 : Math.floor((left+right)/2)
부분 분할 : left = mid+1; right = mid - 1;
종료 조건 : left <= right 또는 left<right

//while 문으로 구현한 이진탐색
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  
  return -1;  // 찾는 요소가 배열에 없는 경우
}

//재귀함수 식으로 구현한 이진 탐색
function binarySearch(arr, target, left = 0, right = arr.length - 1) {
  if (left > right) {
    return -1;  // 찾는 요소가 배열에 없는 경우
  }
  
  const mid = Math.floor((left + right) / 2);
  if (arr[mid] === target) {
    return mid;
  } else if (arr[mid] < target) {
    return binarySearch(arr, target, mid + 1, right);
  } else {
    return binarySearch(arr, target, left, mid - 1);
  }
}

이진트리 구현

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

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)
  }
}

참고

[프로그래머스] 표현 가능한 이진트리 (JavaScript)
[JS] 프로그래머스 - 표현 가능한 이진트리 해설포함 : 이진탐색 개념 정리