[LeetCode] 823. Binary Trees With Factors

Chobby·2026년 10월 15일

JavaScript js ts typescript 기술 기초 면접 문제 알고리즘 연습 이직 코딩 코테 테스트 풀이 프로그래밍

LeetCode

목록 보기

1160/1173

문제

1보다 큰 서로 다른 정수 배열 arr가 주어집니다. 각 숫자를 여러 번 써서 이진 트리를 만들 수 있는데, 리프가 아닌 노드의 값은 두 자식 값의 곱이어야 합니다. 만들 수 있는 트리의 개수를 10^9 + 7로 나눈 나머지를 구합니다.

Input: arr = [2,4,5,10]
Output: 7
// [2], [4], [5], [10], [4,2,2], [10,2,5], [10,5,2]

1 <= arr.length <= 1000
2 <= arr[i] <= 10^9

첫 시도: 찾을 때마다 +1

내림차순으로 정렬하고, 각 값을 나눠 떨어지는 몫이 배열에 있으면 트리 하나를 센 뒤 왼쪽 자식으로 다시 내려가는 방식으로 풀었습니다.

function numFactoredBinaryTrees(arr: number[]): number {
    const arrLen = arr.length
    let trees = arrLen;

    const sorted = arr.toSorted((a, b) => b - a);
    const arrSet = new Set(arr);

    function backTrack(i: number) {
        for (let j = i + 1; j < arrLen; j++) {
            const quot = sorted[i] / sorted[j];
            if (arrSet.has(quot)) {
                trees++;
                backTrack(j);
            }
        }
    }

    for (let i = 0; i < arrLen; i++) backTrack(i);

    return trees;
};

예제는 통과했지만 제출하면 틀립니다.

무엇이 문제였나

1. 경우의 수를 곱하지 않고 더했다

루트 x의 자식이 (a, b)라면 왼쪽 서브트리와 오른쪽 서브트리를 독립적으로 고를 수 있습니다. 그래서 그 루트로 만들 수 있는 트리 수는 (a의 트리 수) × (b의 트리 수)입니다.

첫 코드는 왼쪽 자식만 재귀로 펼쳤고, 오른쪽 자식(몫)은 항상 리프로 취급했습니다.

반례는 [2, 4, 16]입니다.

2: [2] → 1개
4: [4], [4,2,2] → 2개
16: 자식이 (4, 4)이므로 1 + 2 × 2 = 5개

정답은 1 + 2 + 5 = 8인데, 첫 코드는 [16,4,[4,2,2]]와 [16,[4,2,2],[4,2,2]]를 빠뜨려 6을 반환합니다. 예제 2가 맞은 건 오른쪽 자식을 펼칠 일이 한 번도 없었기 때문입니다.

2. 메모이제이션이 없었다

같은 값의 서브트리를 부를 때마다 처음부터 다시 셉니다. 정답이 10^9 + 7로 나눠야 할 만큼 커질 수 있는데 1씩 올려서 세면 끝나지 않습니다.

3. 나머지 연산이 없었다

개선: 반환값 + 메모이제이션

backTrack(i)가 전역 변수를 올리는 대신 sorted[i]를 루트로 하는 트리 수를 반환하게 바꿨습니다.

backTrack(i) = 1 + Σ backTrack(j) × backTrack(k)
               (sorted[j] × sorted[k] = sorted[i])

function numFactoredBinaryTrees(arr: number[]): number {
    const arrLen = arr.length
    const MOD = BigInt(Math.pow(10, 9) + 7);

    const sorted = arr.toSorted((a, b) => b - a);
    const indexOf = new Map<number, number>(sorted.map((v, i) => [v, i]));

    const memo: bigint[] = [];

    function backTrack(i: number) {
        if (memo[i]) return memo[i];
        let trees = 1n;
        for (let j = i + 1; j < arrLen; j++) {
            const quot = sorted[i] / sorted[j];
            const k = indexOf.get(quot);
            if (k) trees += backTrack(j) * backTrack(k);
        }
        return memo[i] = trees % MOD;
    }

    let total = 0n;
    for (let i = 0; i < arrLen; i++) total += backTrack(i);

    return Number(total % MOD);
};

포인트

Set → Map: 몫의 트리 수까지 알아야 하니 값이 배열에 있는지만으로는 부족합니다. 값으로 인덱스를 찾을 수 있게 Map을 씁니다.
좌우 순서: [10,2,5]와 [10,5,2]는 다른 트리입니다. j가 2를 가리킬 때 한 번, 5를 가리킬 때 한 번 잡히므로 따로 처리하지 않아도 두 경우가 모두 세어집니다.
소수 몫: 10 / 4 = 2.5처럼 나눠 떨어지지 않으면 Map에 없으니 자연스럽게 건너뜁니다.
if (k)가 안전한 이유: 인덱스 0은 falsy라 걸러지지만, 0번은 배열의 최댓값이고 몫은 항상 sorted[i]보다 작으므로 몫이 0번일 수 없습니다.
BigInt: 나머지를 취한 두 값의 곱은 최대 약 10^18이라 Number.MAX_SAFE_INTEGER(약 9 × 10^15)를 넘습니다. 그래서 곱셈은 BigInt로 합니다.