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

📙 1. 문제

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

프로그래머스

문제 설명

풀이 1 : 런타임 에러

풀이 과정

1. 2진수로 변환 : toString(2)

2. 트리로 만들기 : makeTree(), (2**n)-1보다 작은 값이 되면 앞에 0을 붙여줌

3. 각 경우 별 트리의 조건에 성립하는지 판단 -> 트리인지 체크하는 함수 (재귀함수)

- "부모 요소가 0일 때, 자식 노드가 1이라면 이진트리 형태가 아니다. 그 외의 형태는 이진트리이다."를 이용

- 맨 처음 함수를 실행할 때 start = 0, end = number.length-1로 두어 mid가 정 가운데 루트노드를 찾을 수 있도록 한다.

- left_c는 부모노드로부터 뻗어 나온 왼쪽 자식 노드, right_c는 오른쪽 자식 노드이다.

- start와 end를 조정해 가며 재귀적 호출을 통해 서브트리 검사를 수행한다.

function solution(numbers) {
    const makeTree = (number) => {
        let [num,temp] = [0,1];
        while(num<number.length){
            num+=temp;
            temp*=2;
        }
        number = '0'.repeat(num-number.length)+ number ;
        return [number, 0, number.length-1]
    }
    
    function isTree ([b_str, start, end]) {
        //부모 노드 idx
        const mid = Math.floor((start+end) / 2);
        //자식 노드 idx
        const left_c = Math.floor((start + mid-1)/2);
        const right_c = Math.floor((mid+1 + end)/2);

        //리프노드 도달
        if (start == end) {
            return true;
        }

        //부모가 0 인데 자식에 1이 있으면 안됨 -> 이 경우 false 를 반환
        if (b_str[mid] === '0' && ((b_str[left_c] === '1') || (b_str[right_c] === '1'))) {
            return false;
        }

        if (!isTree([b_str, start, mid-1])) return false;
        if (!isTree([b_str, mid+1, end])) return false;
        return true;
    }

    return numbers.map(v=>isTree(makeTree(v.toString(2)))?1:0)

}

 

---

🤔 2. 느낀 점

처음에는 문제의 복잡성에 압도되어 조금 겁이 났지만, 한 번 풀이 방법을 성공적으로 도출하게 되니 문제가 순조롭게 해결되었다. Lv3인 만큼 그 정답률도 상대적으로 낮아서 처음에는 두려움이 크게 다가왔지만, 문제를 다 풀어보니 내가 처음에 생각했던 것 보다 그렇게 어렵지 않았다는 것을 느꼈다.

 

🤩 3. 한 번 더 짚고 갈 점

이진 탐색

(포화)이진트리

루트 노드 : tree [Math.floor((start+end)/2)]

루트 노드의 왼쪽 자식 노드 : tree [Math.floor(start+mid-1)/2)

루트 노드의 오른쪽 자식 노드 : tree [Math.floor(mid+1+end)/2)

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