(LeetCode) House Robber ③ with Python

House Robber

📌 시간복잡도 

 

O(n)

 

: DFS를 이용해서 코드를 작성했기에 N번의 연산횟수를 가진다.

📌 공간복잡도 

 

O(n)

 

Problem

The thief has found himself a new place for his thievery again.

: 도둑은 다시 도둑의 새로운 장소를 찾았다.

There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house.

: 이 지역에는 "루트"라고하는 입구가 하나뿐입니다. "루트" 외에 각 집에는 하나의 부모 집이 있습니다.

After a tour, the smart thief realized that "all houses in this place forms a binary tree".

: 견학 후 똑똑한 도둑은 "이곳의 모든 집이 이진 트리를 형성한다"는 것을 깨달았습니다.

It will automatically contact the police if two directly-linked houses were broken into on the same night.

: 같은 날 밤 직접적으로 연결된 집 2 채를 털게되면 자동으로 경찰에 연락한다.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

: 도둑이 경찰에 알리지 않고 오늘 밤 도둑질 할 수있는 최대 금액을 결정하십시오.

 

---

Example 1:

 

Input: [3,2,3,null,3,null,1]

 

Output: 7

Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

 

 

Example 2:

 

Input: [3,4,5,1,3,null,1]

 

Output: 9

Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

 

---

 

💯 Solution

- 해당 문제에서 제일 중요한 포인트는, (1) root를 포함한 경우 (2) root를 포함하지 않은 경우 중에서 큰 값을 반환하면 된다.

- Tree문제에서 root 값으로는 밑에 있는 값이 나온다.

TreeNode{val: 3, left: TreeNode{val: 2, left: None, right: TreeNode{val: 3, left: None, right: None}}, right: TreeNode{val: 3, left: None, right: TreeNode{val: 1, left: None, right: None}}}

 

class Solution(object):
    def rob(self, root):
        '''
        :type root: TreeNode
        :rtype: int
        '''
        # rob_helper는 튜플 형태의 값을 반환
        # 첫 번째 값으로는, root를 포함한 경우 / 두 번째 값으로는, root를 포함하지 않은 경우
        # 둘 중에서 큰 값을 리턴해주면 된다.
        best_with_root, best_without_root = self.rob_helper(root)
        return max(best_with_root, best_without_root)
 
    def rob_helper(self,root):
        # root가 False라면
        if not root:
            return (0,0)
 
        # root 의 왼쪽 줄기가 루트를 포함한 경우와 포함하지않은 경우
        best_with_root_left, best_without_root_left = self.rob_helper(root.left)
        with_root_left, without_root_left = best_without_root_left, max(best_with_root_left, best_without_root_left)
 
        best_with_root_right, best_without_root_right = self.rob_helper(root.right)
        with_root_right, without_root_right = best_without_root_right, max(best_with_root_right, best_without_root_right)
 
        # return 의 첫번째 값은 루트를 포함한 경로 / 두번째 값은 루트를 제외한 경로이다.
        return (root.val + with_root_left + with_root_right, without_root_left + without_root_right)

 

 

📚 참고

leetcode.com/problems/house-robber-iii/discuss/79358/Two-Python-solutions