823. Binary Trees With Factors
https://leetcode.com/problems/binary-trees-with-factors/
문제
풀이(해시 테이블)
이 문제는 바이너리 트리에 관한 문제라고 바이너리 트리쪽으로 생각하면 안되는 문제이다. 바이너리 트리에서 총 개수를 구할 때에는 left * right를 생각하는 것이 키포인트이다.
arr = [2, 3, 4, 12]라고 생각해보자
i = 0일 때 arr = [2] 이므로 dp[2] = 1이 된다.
i = 1일 때 arr = [2, 3]이고 3 % 2는 0이 아니기에 dp[3] = 1이 된다.
i = 2일 때 arr = [2, 3, 4]이고 left = 3이라 하면 right = 4 // 3 인데 나누어 떨어지지 않으므로 넘어간다. 반면에 left = 2이라고 하면 right = 4 // 2 = 2이므로 dp[2] x dp[2] = 1이 된다. 즉 자기자신 + 1 = 2가 된다.
i = 3일 때 arr = [2, 3, 4, 12]이고 left = 4라고 하면 right = 12 // 4 = 3이 되고 dp[4] x dp[3] = 2가 된다.
또한 left = 3이라하면 right = 12 // 3 = 4가 되고 dp[3] x dp[4] = 2가 된다.
반면에 left = 2라하면 right = 12 // 2 = 6이 되지만 dp[6]은 존재하지 않으므로 넘어간다. 즉 자기자신 + 2+ 2 = 5가 된다.
다 합한 값을 리턴해주면 된다.
이것을 코드로 나타내면 다음과 같다.
즉 나누어 떨어지지 않으면 넘어가고 나누어 떨어지고 dp안에 있는 수라면 left x right를 해준다.
결과(해시 테이블)
