프로그래머스 [Lv. 3] 표현 가능한 이진트리 {언어 : JavaScript} [다시 풀어 보기]

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/150367?language=javascript#

프로그래머스

정답 코드

function solution(numbers) {
    const answer = [];
    const ranges = new Array(51).fill().map((_, i) => 2**i - 1);
    
    const adjustOne = (binary) => {
        const lenB = binary.length;
        for (const r of ranges) {
            if (lenB <= r) {
                return r - lenB;
            }
        }
    };
    
    // 표현 가능한 이진트리인지 확인
    const isValid = (arr, node, depth) => {
        if (depth === 0) {
            return true;
        }

        const leftChild = node - depth;
        const rightChild = node + depth;

        // 현재 노드가 0인데 자식 노드가 있다면 표현 불가능함
        if (arr[node] === 0 && (arr[leftChild] === 1 || arr[rightChild] === 1)) {
            return false;
        }

        const half = Math.floor(depth / 2);
        const leftValid = isValid(arr, leftChild, half);
        const rightValid = isValid(arr, rightChild, half);

        return leftValid && rightValid;
    };
    
    for (const number of numbers) {
        const binary = [];
        let tmp = number;
        
        while (tmp > 0) {
            binary.push(tmp % 2);
            tmp = Math.floor(tmp / 2);
        }

        const padding = adjustOne(binary);
        for (let i = 0; i < padding; i++) {
            binary.push(0);
        }

        binary.reverse();

        const lenB = binary.length;
        const isCompleteTree = isValid(binary, Math.floor(lenB / 2), Math.floor((lenB + 1) / 4));
        answer.push(isCompleteTree ? 1 : 0);
    }
    
    return answer;
}

풀이 방법

1. 이진수 변환 및 길이 조정

우선 각 숫자를 이진수로 변환하고, 이 이진수의 길이를 완전 이진트리의 형태(2^k - 1 길이)에 맞게 조정한다.

• 이진수 변환: 숫자를 2로 나눈 나머지를 이용해 이진수로 변환한다.
• 길이 조정: 이진수의 길이를 완전 이진 트리의 길이에 맞추기 위해 필요한 0을 추가한다.

2. 완전 이진 트리 유효성 검사

완전 이진 트리로 변환된 이진수가 실제로 완전 이진트리의 속성을 만족하는지 확인한다.

• 유효성 검사 함수 (isValid): 이 함수는 주어진 배열이 완전 이진 트리인지 재귀적으로 확인합니다. 특정 노드가 0일 때 그 자식 노드가 1이면 안 되는 조건을 확인한다.
• 재귀적 검사: 배열의 가운데 노드를 기준으로 좌우 자식 노드를 재귀적으로 검사합니다. 각 단계에서 자식 노드가 유효한지 확인한다.

3. 결과 저장 및 반환

각 숫자에 대해 완전 이진 트리의 속성을 만족하는지 검사한 결과를 answer 배열에 저장하고, 최종적으로 이 배열을 반환한다.

느낀 점

• 부모 노드에서 유효성 검사를 시작하면 된다는 것을 거꾸로 올라가다 보니 풀기 어려웠다.
• 이진트리에 대한 이해도를 높일 필요가 있다.