JS) 표현 가능한 이진트리

문제

https://school.programmers.co.kr/learn/courses/30/lessons/150367#qna

프로그래머스

이 문제에서 가장 헷갈렸던 부분은 

이렇게 같은 모댱의 트리를 가져도 값이 다를 수 있다는 점이었다. 결국 더미노드의 개수 차이로 인하여 값이 바뀌는 것이 핵심이다.

그리고 가장 중요한 개념은 포화 이진 트리의 개수는 2^h-1개 라는 것이 중요했다.

정답 및 풀이

정답

function checkTree(binary) {
  let len = binary.length;
  let mid = Math.floor(len / 2);
  let left = binary.slice(0, mid);
  let right = binary.slice(mid + 1);

  if (len < 3) return true;
  else if (+binary[mid] === 0) return false;
  else {
    let chkLeft = true,
      chkRight = true;

    if (left.replace(/0/g, "") !== "") {
      chkLeft = checkTree(left);
    }
    if (right.replace(/0/g, "") !== "") {
      chkRight = checkTree(right);
    }

    return chkLeft && chkRight;
  }
}

function solution(numbers) {
  let answer = [];

  for (let num of numbers) {
    let binary = num.toString(2);
    let targetH,
      i = 1;
    const binaryLen = binary.length;

    if (num === 0) {
      answer.push(0);
      continue;
    }

    while (true) {
      if (binaryLen === 2 ** i - 1) break;
      else if (binaryLen > 2 ** i - 1) {
        i++;
      } else {
        targetH = i;
        break;
      }
    }

    if (targetH) {
      binary = "0".repeat(2 ** i - 1 - binaryLen) + binary;
    }

    checkTree(binary) ? answer.push(1) : answer.push(0);
  }

  return answer;
}

풀이

  for (let num of numbers) {
    let binary = num.toString(2);
    let targetH,
      i = 1;
    const binaryLen = binary.length;

    if (num === 0) {
      answer.push(0);
      continue;
    }

    while (true) {
      if (binaryLen === 2 ** i - 1) break;
      else if (binaryLen > 2 ** i - 1) {
        i++;
      } else {
        targetH = i;
        break;
      }
    }

    if (targetH) {
      binary = "0".repeat(2 ** i - 1 - binaryLen) + binary;
    }

    checkTree(binary) ? answer.push(1) : answer.push(0);
  }

1. for문으로 numbers를 돌면서 값을 확인
2. binary에 num의 2진수 값을 저장, targetH에는 가장 가까운 2^h-1을 저장 할 예정
3. 만약에 num이 0이면 바로 0을 answer에 저장
4. while 문을 통해 가장 가까운 2^h-1의 h 값을 변수 targetH에 저장
   (만약 2^h-1과 값이 딱 일치하면 targetH에는 아무것도 저장되지 않음)
5. 만약 targetH가 존재하면 포화 이진 트리의 조건을 맞추기 위해서 binary의 왼쪽에 "0"을 (2^targetH-1 - binaryLen)개 추가해야됨
6. checkTree 함수를 통해 구현이 가능한지 확인하고 answer에 0이나 1을 추가

function checkTree(binary) {
  let len = binary.length;
  let mid = Math.floor(len / 2);
  let left = binary.slice(0, mid);
  let right = binary.slice(mid + 1);

  if (len < 3) return true;
  else if (+binary[mid] === 0) return false;
  else {
    let chkLeft = true,
      chkRight = true;

    if (left.replace(/0/g, "") !== "") {
      chkLeft = checkTree(left);
    }
    if (right.replace(/0/g, "") !== "") {
      chkRight = checkTree(right);
    }

    return chkLeft && chkRight;
  }
}

1. 넘어온 값의 길이인 len, 값의 중간 위치인 mid, 왼쪽 부분인 left, 오른쪽 부분인 right
2. 만약 길이가 3 미만이면 여태 불합격 조건에 안걸린거라서 true 반환
3. 만약 가운데가 0이면 그 숫자는 트리로 표현할 수 없어서 false 반환
4. 만약 left나 right가 전부 다 0이면 모두 더미 노드로 이루어져서 가능한 것이라 true를 반환하고, 최종적으로 (left의 값) && (right의 값)을 반환