[Mock] Google 13

1672. Richest Customer Wealth

You are given an m x n integer grid accounts where accounts[i][j] is the amount of money the ith customer has in the jth bank. Return the wealth that the richest customer has.

A customer's wealth is the amount of money they have in all their bank accounts. The richest customer is the customer that has the maximum wealth.

My Answer 1: Accepted (Runtime: 52 ms - 79.45% / Memory Usage: 14.2 MB - 83.95%)

class Solution:
    def maximumWealth(self, accounts: List[List[int]]) -> int:
        ans = 0
        for i in range(len(accounts)):
            ans = max(ans, sum(accounts[i]))
        
        return ans

accounts 의 합 중에 최댓값 찾아서 ans 에 넣어주기

---

1506. Find Root of N-Ary Tree

My Answer 1: Time Limit Exceeded (37 / 39 test cases passed.)

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []
"""

class Solution:
    def findRoot(self, tree: List['Node']) -> 'Node':
        while None in tree:
            tree.remove(None)
        
        if tree is None:
            return []
        
        num = len(tree)
        self.dic = {}
        
        def func(root, level):
            if root is None:
                return level
            
            lev = 0
            for i in range(len(root.children)):
                if root.children[i] in self.dic:
                    lev = max(lev, self.dic[root.children[i]])
                else:
                    lev = max(lev, func(root.children[i], level + 1))
            
            return level + lev
        
        for i in range(len(tree)):
            if tree[i] == None:
                continue
            self.dic[tree[i]] = func(tree[i], 1)
        
        m = max(self.dic.values())
        
        for k, v in self.dic.items():
            if v == m:
                return k
                
        return []

재귀 함수로 각 노드마다 level 을 계산해서 가장 큰 level 을 가진 노드를 return

level 은 dic 에 저장해서
children 중에 이미 존재하는 값은 dic 값으로 바로 사용

Solution 1: Accepted

class Solution:
    def findRoot(self, tree: List['Node']) -> 'Node':        
        c = {}
        n = {}
        for node in tree:            
            n[node.val] = node
            if node.children is not None:
                for ch in node.children:                    
                    c[ch.val] = True
        for k in n:
            if k not in c:
                return n[k]
        return None

parent 가 없는 Node return 하기

테스트케이스 적용하기가 넘 복잡해서 힘드네요...^^

---

429. N-ary Tree Level Order Traversal

Given an n-ary tree, return the level order traversal of its nodes' values.

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

My Answer 1: Accepted (Runtime: 52 ms - 70.71% / Memory Usage: 16.1 MB - 58.16%)

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        if root is None:
            return []
        
        ans = [[root.val]]
        queue = [root]
        
        while queue:
            num = len(queue)    # 같은 level 의 개수
            tmp = []
            for _ in range(num):
                r = queue.pop(0)

                if r.children:
                    for i in range(len(r.children)):
                        tmp.append(r.children[i].val)
                        queue.append(r.children[i])
            if tmp:
                ans.append(tmp)
        
        return ans

1. root 가 None 일 때 예외처리

2. ans 에 초기값으로 [root.val] 넣어주고
   level-order 로 보기 위해 queue 이용하기

3. queue 의 길이 == 각 level 의 노드 개수
   => 길이만큼 for 문 돌려서 노드들을 pop 해준 다음
   children 이 있으면 tmp 에는 val 값들만, queue 에는 children 들을 저장

4. level 에 값이 하나 이상 존재할 때만 ans 에 append

이 문제가 아니었음..^^