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

목차

1. 문제 출처
2. 문제 설명
3. 제한 조건
4. 정답

 

문제 출처

Lv.3 표현 가능한 이진트리 - JavaScript

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

프로그래머스

문제 설명

당신은 이진트리를 수로 표현하는 것을 좋아합니다.

이진트리를 수로 표현하는 방법은 다음과 같습니다.

이진수를 저장할 빈 문자열을 생성합니다.
주어진 이진트리에 더미 노드를 추가하여 포화 이진트리로 만듭니다. 루트 노드는 그대로 유지합니다.
만들어진 포화 이진트리의 노드들을 가장 왼쪽 노드부터 가장 오른쪽 노드까지, 왼쪽에 있는 순서대로 살펴봅니다. 노드의 높이는 살펴보는 순서에 영향을 끼치지 않습니다.
살펴본 노드가 더미 노드라면, 문자열 뒤에 0을 추가합니다. 살펴본 노드가 더미 노드가 아니라면, 문자열 뒤에 1을 추가합니다.
문자열에 저장된 이진수를 십진수로 변환합니다.
이진트리에서 리프 노드가 아닌 노드는 자신의 왼쪽 자식이 루트인 서브트리의 노드들보다 오른쪽에 있으며, 자신의 오른쪽 자식이 루트인 서브트리의 노드들보다 왼쪽에 있다고 가정합니다.

제한 조건

• 1 ≤ numbers의 길이 ≤ 10,000
  
  • 1 ≤ numbers의 원소 ≤ 1015

입출력 예

numbers	result
[7, 42, 5]	[1, 1, 0]
[63, 111, 95]	[1, 1, 0]

정답

function solution(numbers) {
    // numbers 배열의 각 요소에 대해 checkNumber 함수를 호출하여 결과 배열을 반환
    return numbers.map(checkNumber);
}

// 주어진 숫자를 완전 이진 트리로 변환하여 유효성 검사 후, 결과(1 또는 0)를 반환하는 함수
function checkNumber(number) {
    // 주어진 숫자를 완전 이진 트리 형태의 이진 문자열로 변환
    const binaryStr = convertToCompleteBinary(number);
    // 변환된 이진 문자열이 완전 이진 트리인지 검사하고 결과를 반환
    return isValidCompleteBinary(binaryStr) ? 1 : 0;
}

function convertToCompleteBinary(number) {
    const binNum = number.toString(2);
    const treeHeight = Math.ceil(Math.log2(binNum.length + 1));
    // 완전 이진 트리의 노드 수 계산
    const totalNodes = 2 ** treeHeight - 1;

    // 완전 이진 트리 형태로 패딩하여 이진 문자열 반환
    return '0'.repeat(totalNodes - binNum.length) + binNum;
}

function isValidCompleteBinary(binaryStr) {
    const midIndex = Math.floor(binaryStr.length / 2);
    const mid = binaryStr[midIndex];
    
    // 중간 값이 0이고 문자열 내에 1이 존재하면 유효하지 않은 것으로 판단
    if (mid === '0' && binaryStr.indexOf('1') !== -1) return false;
    // 이진 문자열의 길이가 1이면 유효한 것으로 판단
    if (binaryStr.length === 1) return true;

    // 이진 문자열의 왼쪽과 오른쪽 부분을 재귀적으로 검사
    return (
        isValidCompleteBinary(binaryStr.slice(0, midIndex)) &&
        isValidCompleteBinary(binaryStr.slice(midIndex + 1))
    );
}