[Leetcode 823] Binary Trees With Factors

Given an array of unique integers, arr, where each integer arr[i] is strictly greater than 1.

We make a binary tree using these integers, and each number may be used for any number of times. Each non-leaf node's value should be equal to the product of the values of its children.

Return the number of binary trees we can make. The answer may be too large so return the answer modulo 109 + 7.

 

Example 1:

Input: arr = [2,4]
Output: 3
Explanation: We can make these trees: [2], [4], [4, 2, 2]

Example 2:

Input: arr = [2,4,5,10]
Output: 7
Explanation: We can make these trees: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].

 

Constraints:

• 1 <= arr.length <= 1000
• 2 <= arr[i] <= 109
• All the values of arr are unique.

처음에 dp로 생각해서 풀까했다.

2 3 6 12 로 주어진 경우

12 = 2*6 = 3*4 = 6*2 이렇게 볼 수 있다.

2부터 차근차근 서브트리로 몇 개를 만들 수 있는지 기록하고 나중에 사용하려고 했는데

dp[2] = 1, dp[6] = 1 + dp[2]*dp[3]*2 = 3

이렇게 dp[12] = 1 + dp[2]*dp[6]*2 = 7인데

사실은 12 = 12*1 = 6*2 = 2*6 = 3*2*2 = 2*3*2 = 2*2*3 총 6개다.

2*3*2가 중복으로 세어진다. 

dp[2] * dp[6] = 2 * (3*2)

= (2*3) * 2 = dp[6] * dp[2]라서.

..

라고 생각했는데

그림이 다르다.

편리하게 표현한다고 (2 3 2) 이런식으로만 표현했더니 문제의 방향 자체를 잊고 뻘 생각을 하고 있었다..

정확히는 [12 2 6 3 2] [12 6 2 3 2] 으로 다른 경우인데.

함정을 찾았다고 좋아했는데 그냥 나 혼자 뻘 짓을 하고 있었던 것이다.. 처음 생각한대로 푸는 게 맞았다.

 

class Solution(object):
    def numFactoredBinaryTrees(self, arr):
        """
        :type arr: List[int]
        :rtype: int
        """
        # (self, A: List[int]) -> int:
        arr.sort()
        fmap, ans = defaultdict(), 0
        m = 10**9+7
        for num in arr:
            ways, lim = 1, sqrt(num) # 혼자 루트를 이루는 트리는 항상 되니까 1은 기본
            for fA in arr:
                if fA > lim: break # 효율성 때문에 추가. arr는 정렬되어있고, 똑같은 계산을 안하기 위해
                fB = num / fA
                if num % fA == 0 and fB in fmap:
                    ways += fmap[fA] * fmap[fB] * (1 if fA == fB else 2)
            fmap[num], ans = ways, (ans + ways)
        return ans % m

num % fA == 0을 확인하는 게 중요하다. num = 5, fA = 2일 때 fB = 2인데 사실 나눠진 건 아니니까. casting 때문 !!

 

복잡도

time

O(N*N)) = O(N^2)

해당 숫자의 제곱근 이하인 fA만 확인하긴 하는데 최악의 경우는 N번 다 돌아야 하는 게 맞으니까.

 

space

O(N)

 

Runtime: 115 ms, faster than 100.00% of Python online submissions for Binary Trees With Factors.

Memory Usage: 13.5 MB, less than 92.31% of Python online submissions for Binary Trees With Factors.

오호라 100%... 시간 줄이려고 제곱근 처리 해주고 애써서 그런지 100%가 나왔다!

 

 

참고사이트

https://dev.to/seanpgallivan/solution-binary-trees-with-factors-2kk4

Solution: Binary Trees With Factors

→ 여기 나온 거에서 한 줄 추가했다.

https://shareablecode.com/snippets/binary-trees-with-factors-python-solution-leetcode-qyJ8-DDGH

Binary Trees With Factors - Python Solution @ LeetCode