Leet Code : 823. Binary Trees With Factors

823. Binary Trees With Factors

var numFactoredBinaryTrees = function(arr) {
    const trees = {}
    const mod = 10 ** 9 + 7
    const sortedArr = arr.sort((a, b) => a-b)
    
    let answer = 0
    sortedArr.forEach((num) => {
        let result = 0
        result += 1
        
        for (let i=2; i<parseInt(num ** (1/2))+1; i++) {
            const otherNum = parseInt(num/i)
            if(i * otherNum === num && !!trees[i] && !!trees[otherNum]) {
                if (i !== otherNum) {
                    result += trees[otherNum] * trees[i]
                    result %= mod
                } 
                result += trees[otherNum] * trees[i]
                result %= mod
            } 
        }
        
        trees[num] = result % mod
        answer += result
        answer %= mod
    })
    return answer
};

풀이 방법

1. arr배열을 오름차순으로 정렬한다.
2. 값이 작은 숫자 부터 rootNode일때 가질 수 있는 트리의 경우의 수를 계산합니다.
   1. 그리고 부모노드의 값은 2개의 자식 노드의 곱한 값이 되어야 하므로
   2. 2 ~ 부모노드의 루트값의 범위로 루프문을 만들어서 가능한 자식 서브트리의 경우의 수 를 계산 합니다.
   3. 이미 작은 노드 부터 트리의 경우의 수를 계산해 왔기 때문에 빠르게 계산 가능합니다.
3. 그 트리의 경우의 수를 trees객체에 저정합니다.