823. Binary Trees With Factors

• Array arr에 있는 숫자를 이용해서 만들 수 있는 트리의 경우의 수를 구하는 문제.
• 트리의 non leaf node 숫자는 child node 숫자의 곱으로 결정되어야하는 규칙이 있으므로 이를 바탕으로 경우의 수를 계산해보면 된다.
• 처음에는 두 숫자의 조합을 바탕으로 숫자의 곱이 array arr에 존재하는지 체크하고 있으면 이를 바탕으로 트리를 만들어 root 부터 탐색하는 방식을 취했다.
• child node 의 숫자가 다른 경우
• , 두 가지 순서에 대한 조합의 숫자 + parent node 하나만으로 구성된 트리
• child node의 숫자가 같은 경우
• , 두 가지 순서에 대한 조합의 숫자 ( 경우의 수를 제외) + parent node 하나만으로 구성된 트리
• 이런 방식으로 접근했으나 일부 테스트 케이스에서 실패했으며 원인을 찾지 못해서 해답을 참조했다.

• child node 숫자 조합에서 parent node 숫자를 만들어내는 방식보다는 반대로 접근하는 방식이 더 효율적이고 쉽게 풀 수 있는 것으로 생각된다.

• 풀이 방식은 다음과 같다.
• 먼저 array arr를 작은 숫자가 앞으로 오도록 오름차순으로 정렬한다.
• 각 node 별 결과를 계산하여 저장한다.
• root node와 factor node (child node) 조합을 기준으로 나머지 child node를 계산한다.
• root 숫자가 factor로 나뉘지 않는다면 해당되는 child node 조합이 존재하지 않는 것이므로 skip 한다.
• 당연하지만 factor가 root랑 같거나 크면 child node 조합이 존재하지 않으므로 (숫자는 1보다 큰 값이어야 하니까) skip 한다.
• 나머지 노드 quotient는 root / factor로 결정된다.
• 현재 노드 root의 경우의 수는 factor, quotient node 각각의 경우의 수의 곱의 합이다.
• 이렇게 계산된 각 노드 별 경우의 수 subResult 를 모두 더하면 전체 경우의 수가 된다. 여기에 모듈러 연산을 하면 된다.

class Solution {
public:
    static constexpr int MOD = 1e9 + 7;

    int numFactoredBinaryTrees(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        long long result = 0;
        unordered_map<int, long> subResult;
        for (auto root : arr) {
            subResult[root] = 1;
            for (auto factor : arr) {
                if (factor >= root) break;
                if (root % factor != 0) continue;
                int quotient = root / factor;
                if (subResult.find(quotient) != subResult.end()) {
                    subResult[root] += subResult[factor] * subResult[quotient];
                }
            }
        }
        for (auto& entry : subResult) {
            result += entry.second;
        }
        return result % MOD;
    }
};