개요

해외에서는 엔지니어의 면접에 있어서 코딩 테스트라고 하는 것이 행해지는 것 같고, 많은 경우, 특정의 함수나 클래스를 주제에 따라 실장한다고 하는 것이 메인이다.

그 대책으로서 LeetCode 되는 사이트에서 대책을 실시하는 것 같다.

빠른 이야기가 본고장에서도 행해지고 있는 것 같은 코딩 테스트에 견딜 수 있는 알고리즘력을 단련하는 사이트.

모처럼 하고 사람 수준의 알고리즘력 정도는 가지고 두는 것이 좋겠다는 것으로 부정기적으로 문제를 풀어 그 때에 생각한 방법을 메모적으로 써 갈까 생각합니다.

Leetcode

기본적으로 easy의 acceptance가 높은 순서에서 풀어 갈까 생각합니다.

지난번
0부터 시작하는 LeetCode Day7 「104. Maximum Depth of Binary Tree」

문제

1302. Deepest Leaves Sum

첫 Medium입니다.
이번 문제도 good의 수가 많아, 좋은 문제라고 생각했으므로 풀어 보았습니다.

문제는 매우 간단하고, 이분 나무가 주어지기 때문에 가장 깊은 잎의 합계치를 돌려준다는 것이군요. 최근 나무 관련의 문제가 많은 생각이 든다···
또한, 예는 다음과 같습니다.Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8] Output: 15
이 경우 가장 깊은 잎이 7과 8이므로 더해 15라는 것이군요.



문제를 확실히 본 느낌으로는 깊이 우선 탐색으로 한결같이 모든 잎의 깊이를 조사해 깊이와 값을 돌려준다, 라고 하는 것이 간단한 생각인가라고 생각했습니다.
다만, 그러면 조금 중복적인 코드가 되어 버리는 생각이 들었고, 깊이를 조사할 때 동시에 해시 테이블을 사용하면 깊이와 값을 모두 보관 유지할 수 있어 효율적으로 쓸 수 있는 것은 아닌가? 라고 생각 구현해 보았습니다.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        ans = {}
        count = 0
        self.dfs(root,ans,count)

        return ans[max(ans)]

    def dfs(self,node,ans,count):
        if node:
            if node.left:
                self.dfs(node.left,ans,count+1)
            if node.right:
                self.dfs(node.right,ans,count+1)
        if count not in ans:
            ans[count] = node.val
        else:
            ans[count] += node.val
# Runtime: 104 ms, faster than 46.02% of Python3 online submissions for Deepest Leaves Sum.
# Memory Usage: 17.4 MB, less than 100.00% of Python3 online submissions for Deepest Leaves Sum.

dfs 함수 안에서 count의 인덱스와 같으면 가산, 그 이외의 경우는 값을 그대로 대입한다, 라고 하는 형식을 취했습니다.
ans 안에서의 최대치를 돌려주면(자) 최종적으로 가장 깊은 잎의 값이 되돌아 온다는 것입니다.
그러나, 이 대답에서는 그다지 빠르지 않네요・・・

discuss를 관측한 범위에서는 이하의 대답이 Python에서 가장 빠르지 않을까 생각합니다.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deepestLeavesSum(self, root):
        q = [root]
        while q:
            pre, q = q, [child for p in q for child in [p.left, p.right] if child]
        return sum(node.val for node in pre)
# Runtime: 84 ms, faster than 98.04% of Python3 online submissions for Deepest Leaves Sum.
# Memory Usage: 17.3 MB, less than 100.00% of Python3 online submissions for Deepest Leaves Sum.

어쨌든 엄청 빠릅니다 ...
지금은 이런 코드 쓸 수 있을 것 같지 않지만, 이런 코드를 읽을 수 있는 것은 매우 재미있네요.

이런 식으로 이렇게 빨라졌어! 라고 하는 예가 있으면 코멘트란에서 코드와 메모리 소비량과 런타임을 써 궁리한 점을 가르쳐 주시면 다행입니다.