[Leetcode 198] House Robber

https://leetcode.com/problems/house-robber/

House Robber - LeetCode

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

 

Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

 

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

3	2	1	5	1
3	2	4	8	5

인접한 집을 털면 안되니까 increasing subsequence긴 한데 바로 왼쪽 원소를 포함하지 않는 최대 subsequence를 찾아야 한다.

0번째, 1번째 원소는 그대로 저장하고 2번째 원소부터 0 ~ i-2 원소까지의 최대 subsequence를 찾아 저장하는 방법으로 시작했다.

 

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) < 3:
            return max(nums)
        else:
            dp = [nums[0], nums[1]]
            for i, val in enumerate(nums):
                if i < 2:
                    continue
                else:
                    dp.append(max(dp[0:i-1])+val)
            return max(dp)

 

constraints에 nums 갯수가 1개, 2개인 경우도 포함되는 건데 바로 dp에 nums[0], nums[1] 저장했다가 런타임 에러 한 번 났다. 이런 것들은 진짜 당연하게 챙겨야 하는 것들인데,, 너무 오래 쉰걸까? 힝구

 

memoizaiton한 것들 중  0 - i-2 까지의 값 중 최대 값을 찾으면 인접하지 않은 집들을 털었을 때의 최댓값 + 지금 집의 값으로 dp에 저장할 수 있다.

찾아보니 python list slicing ([ ]이렇게 범위 지정해서 list의 일부만 만드는 것)이 copy해서 리턴하는 거라서 복잡도가 O(n)이라고 하고, max도 O(n)이라고 한다.

 

복잡도

Time

if에서 리턴하는 건 O(2) = O(1),

else 문에서는 원소 하나씩 다 도는데 slicing 하면서 O(N), max 찾는다고 O(N)이라 N*(N+N) = N^2.

결국 O(N^2)이다.

 

Space

dp에 저장하고, 또 slicing까지 해서.. 결국 O(N)

 

Runtime: 34 ms, faster than 28.72% of Python online submissions for House Robber.
Memory Usage: 13.3 MB, less than 68.91% of Python online submissions for House Robber.

 

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) < 3:
            return max(nums)
        else:
            dp = [nums[0], nums[1], nums[0]+nums[2]]
            sub_max = max(nums[0], nums[1])
            for i, val in enumerate(nums):
                if i < 3:
                    continue
                else:
                    dp.append(sub_max+val)
                    sub_max = max(dp[i-1], sub_max)
            return max(dp)

 

매번 slicing 해서 max 찾는다고 N번 더 돌기 싫어서 좀 바꿔봤다.

i번째 집을 털 때 최대로 얻을 수 있는 값을 구하려면 0 ~ i-2 번째까지 집을 털 때 최대로 얻을 수 있는 값들 미리 계산해 놓은 것들 중 최대값을 찾아서 더한다는 아이디어는 똑같은데 그 최대값을 매번 구하는 게 아니라 아예 저장하는 것으로.

i=2인 집의 최대값은 nums[i]가 0 이상이기 때문에 nums[0] + nums[2]일거고.

i=3인 집을 털 때 최대값은 i = 0, 1인 집의 값 중 큰 값(sub_max) +nums[3]이다. i=2인 집은 어차피 못 터니까. 대신 sub_max를 계속 업데이트 해줘야 한다. i=4인 집을 털 때는 i=2의 최대값도 포함해서 sub_max를 생각해야 하니까, 원래 sub_max랑 비교해서 큰 값으로 업데이트하면 매번 slicing해서 max 찾는 일을 안해도 된다.

 

복잡도

Time

O(N)

 

Space

dp에 저장하니까 O(N)

 

Runtime: 23 ms, faster than 73.22% of Python online submissions for House Robber.
Memory Usage: 13.3 MB, less than 68.91% of Python online submissions for House Robber.

 

메모리 사용량은 아까랑 똑같고, 실행시간은 아주 조금 좋아졌다. 아무래도 constraints 범위가 크지 않아서 큰 차이가 안나는게 아닐까 싶다.