개요

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

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

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

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

Leetcode

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

지난번
처음부터 시작하는 LeetCode Day10 「1431. Kids With the Greatest Number of Candies」

문제

1315. Sum of Nodes with Even-Valued Grandparent

난이도는 Medium입니다.

이분목이 주어져 그 부모의 부모, 즉 조부모의 값이 짝수인 ノードの合計値 를 돌려주도록(듯이) 하면 좋네요.
존재하지 않으면 0를 반환합니다.


Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 18
Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.

Constraints:
The number of nodes in the tree is between 1 and 10^4.
The value of nodes is between 1 and 100.

예는 이와 같이 되어 있으며, 조부모이며 짝수라는 조건에 해당하는 것이 6 와 8 합계 값인 [2,7,1,3]가 반환되었습니다.

해법

문제를 보았을 때 생각해 낸 것은, 현재의 노드, 부모 노드, 그리고 조부모 노드를 슬라이드시키면서 유지해, 만일 조부모 노드가 존재해, 그리고 그 값을 2로 나눈 때의 나머지가 0이면 현재의 노드를 합계치에 가산한다는 생각입니다.
이 사고 방식을 구현한 것이 다음과 같습니다.

# 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:
    ans = 0
    def sumEvenGrandparent(self, root: TreeNode) -> int:
        def dfs(cur:TreeNode,par:TreeNode,gra:TreeNode):
            if gra and gra.val % 2 == 0:
                self.ans += cur.val
            if cur.left:
                dfs(cur.left,cur,par)
            if cur.right:
                dfs(cur.right,cur,par)

        dfs(root,None,None)
        return self.ans
# Runtime: 92 ms, faster than 98.47% of Python3 online submissions for Sum of Nodes with Even-Valued Grandparent.
# Memory Usage: 17.3 MB, less than 100.00% of Python3 online submissions for Sum of Nodes with Even-Valued Grandparent.

이번은 생각이 효율이 좋았던 것 같아 매우 심플하게 걸었습니다. 속도도 충분하고, 꽤 좋은 대답이 나왔다고 생각합니다.

ans의 위치가 신경이 쓰이는 사람이 있을지도 모릅니다만, Python에서는 함수중에서 도중까지는 글로벌 변수를 참조해, 도중으로부터 로컬 변수에 다시 정의할 수 없고, 함수의 어딘가에 로컬 변수로 정의한 변수는 함수에 들어가면 처음부터 로컬 변수로 취급됩니다. 그래서 이런 형태로 되어 있습니다.

왠지 기분이 좋았기 때문에 여러가지 조사해 보면, Python에는 [5] 변수 되는 것이 있는 것을 알았습니다.
함수내에 함수를 정의할 때에, 내측의 함수로부터 외측의 함수내의 변수를 변경하기 위해서 사용하는 것처럼, 사용해 쓰면 이렇게 쓸 수 있습니다.

# 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 sumEvenGrandparent(self, root: TreeNode) -> int:
        def dfs(cur:TreeNode,par:TreeNode,gra:TreeNode):
            if gra and gra.val % 2 == 0:
                nonlocal ans
                ans += cur.val
            if cur.left:
                dfs(cur.left,cur,par)
            if cur.right:
                dfs(cur.right,cur,par)
        ans = 0
        dfs(root,None,None)
        return ans
# Runtime: 92 ms, faster than 98.47% of Python3 online submissions for Sum of Nodes with Even-Valued Grandparent.
# Memory Usage: 17.3 MB, less than 100.00% of Python3 online submissions for Sum of Nodes with Even-Valued Grandparent.

속도도 변하지 않고, 이쪽이 깨끗이 하고 있어 개인적으로는 좋아할지도 모릅니다.