leetcode : Binary Trees With Factors

https://leetcode.com/problems/binary-trees-with-factors/submissions/

Binary Trees With Factors - LeetCode

 

어려웠다.

여러가지 중요한 발상엔 성공했지만 정렬을 생각 못해서 못풀었다.

일단 naive하게 생각하면 O(N^3)이 나오는데 N이 최대 1000인걸 생각하면 1000000000 (10억)번의 연산이 필요하고 TLE가 뜰것이다. O(N^2)까지는 줄여야 한다. 기존 연산결과를 재활용 하는 방향으로 최적화를 시도해봐야 한다. DP를 살짝 의심

 

일단 맨 처음에 주어진 arr에서 숫자를 조합해서 트리를 새로 만들면

새로만든 트리의 루트노드랑 다른 숫자를 결합해 또 트리를 만들 수 있다.

그럼 기존 연산 결과를 활용해 새 트리를 계산할 수 있지 않을까 해서 여기서 DP임을 거의 확신했다.

 

근데 예를 들어 루트노드가 4인 서로다른 트리가 4개 있을 때 이를 2랑 조합해서 8이 루트가 되게하는 트리의 개수를 세려면 그냥 루트노드가 4인 트리의 개수만 알면 되지 않나 싶었다. 4 트리의 개수 * 2 트리의 개수 하면 4랑 2 조합해서 8 트리가 몇개 나올 수 있는지 알수있으니까.

 

정렬이 필요한 이유는 예를 들어 8 트리를 만든다고 쳤을 때 자기보다 작은 숫자만 검사하면 되기 때문이다. 8보다 큰 수를 곱셈연산해서 8을 만들 순 없다. 그래서 정렬은 불필요한 검사를 엄청 많이 줄여줌.

 

count라는 딕셔너리를 만들어서 각 숫자를 루트노드로 하는 트리의 개수가 몇 개인지 저장한다. 마지막에 count 딕셔너리의 value값을 다 더하면 그게 정답이 될것이다.

class Solution:
    def numFactoredBinaryTrees(self, arr: List[int]) -> int:  
        arr.sort()
        
        count = Counter(arr)
        
        for i in range(len(arr)):
            added = 0
            
            for j in range(i):
                if arr[i] % arr[j] == 0:
                    added += count[arr[j]] * count[arr[i]//arr[j]]
            
            count[arr[i]] += added
            
        return sum(count.values()) % (10**9 + 7)