(LeetCode) House Robber ② with Python

House Robber

📌 시간복잡도 

O(n) : for문을 1번 사용

📌 공간복잡도 

O(1) : 변수로 저장하는 것이 없고, 임의로 저장하는 heap memory에 해당하는 dp[i] 값들만 저장공간에 남는다.

Problem

You are a professional robber planning to rob houses along a street.

: 당신은 거리를 따라 집을 강탈하려는 전문 강도이다.

Each house has a certain amount of money stashed. All houses at this place are arranged in a circle.

:  각각의 집에는 일정 금액의 돈이 숨겨져있다. 이 장소의 모든 집은 원으로 배열화되어있다.

That means the first house is the neighbor of the last one.

: 그것은 첫번째 집이 마지막집의 이웃이라는 것을 의미한다.

Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

: 한편, 인접한 집에는 보안시스템이 연결되어있어 같은 날 밤에 인접한 두 집에 침입하면 자동으로 경찰에 연락이 간다.

Given a list of non-negative integers 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 = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

: 만약에 내가 첫번째 집(돈=2)과 세번째 집(돈=2)이 인접해있기 때문에 고를 수 없다.

 

Example 2:

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.

: 강도는 첫번째 집과 세번째 집을 고를 수 있다. (1+3)

 

Example 3:

Input: nums = [0]
Output: 0

: 0일때는 (아무도 돈이없을때) 0을 출력한다.

 

Constraints:

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

 

💯 Solution ①

: 코드 작성 중에, if문과 for문이 많아지게 되어서 다른 코드를 작성해야할 필요성을 느낌..

    
if sum(nums)==0:
    return 0
 
if hosue_cnt==1:
    return sum(nums)
 
## len(nums)가 홀수일 때
# 홀수만 있는 배열 TestList1 / 짝수만 있는 배열 TestList2
if hosue_cnt%2==1:
    TestList1=[]
    TestList2=[]
 
    for i in range(0,hosue_cnt,2):
        if hosue_cnt==3:
            if nums[0] > nums[hosue_cnt - 1]:
                if i == hosue_cnt:
                    continue
                else:
                    TestList1.append(nums[i])
                # 첫번째 값이 마지막 값보다 작은 경우
            elif nums[0] < nums[hosue_cnt - 1]:
                if i == 0:
                    continue
                else:
                    TestList1.append(nums[i])
                # 첫번째 값과 마지막 값이 같은 경우
            else:
                if i == 0:
                    continue
                else:
                    TestList1.append(nums[i])
        else:
            TestList1.append(nums[i])
 
    for j in range(1,hosue_cnt,2):
        TestList2.append(nums[j])
 
    ####### 해당부분은 함수화###########
 
    if sum(TestList1) > sum(TestList2):
        return sum(TestList1)
    elif sum(TestList1) < sum(TestList2):
        return sum(TestList2)
    # 두 경우의 합이 같을 때 (둘 중 아무거나 반환)
    else:
        return sum(TestList1)
 
 
## len(nums)가 짝수일 때
# 인덱스가 짝수인 배열 TestList1 / 인덱스가 홀수인 배열 TestList2
if hosue_cnt%2==0:
    TestList1=[]
    TestList2=[]
 
    # 0,2,4,6,8 ... 짝수 인덱스를 TestList1
    for i in range(0,hosue_cnt,2):
        TestList1.append(nums[i])
 
    # 1,3,5,7,9... 홀수 인덱스를 TestList2
    for j in range(1,hosue_cnt,2):
        TestList2.append(nums[j])
 
 
    ####### 해당부분은 함수화###########
    # 짝수번호의 합이 홀수번호의 합보다 클 때
    if sum(TestList1) > sum(TestList2):
        return sum(TestList1)
    # 짝수번호의 합이 홀수번호의 합보다 클 때
    elif sum(TestList1) < sum(TestList2):
        return sum(TestList2)
    # 두 경우의 합이 같을 때 (둘 중 아무거나 반환)
    else:
        return sum(TestList1)

 

💯 Solution ②

: 동적계획법 (Dynamic Programming) 을 사용해서 작성해보자.

class Solution(object):
    def rob(self,nums):
        '''
        :type nums: List[int]
        :return: int
        '''
        # nums=[1,2,3,4,5]
        def houseRobber(nums):
            # 동적계획법을 사용해보자
            dp=[0]*len(nums)
            dp[0]=nums[0]
            dp[1]=max(nums[0],nums[1])
            for i in range(2, len(nums)):
                dp[i]=max(dp[i-1],nums[i]+dp[i-2])
            # 가장 큰 값을 dp[-1]을 받음
            return dp[-1]
 
        # edge cases:
        if len(nums)==0: return 0
        if len(nums)==1: return nums[0]
        if len(nums)==2: return max(nums)
 
        return max(houseRobber(nums[:-1]),houseRobber(nums[1:]))
 
 

 

점화식을 구해보면, 

 

dp[i] = max(dp[i-1], nums[i]+dp[i-2])

 

릍 통해서 dp 이전 값(dp[i-1)과 nums[i] + dp 이전전값(dp[i-2]) 을 비교해서 큰 값을 반환하는 점화식을 작성한다.

 

 

그리고, 주어진 배열 nums에서

 

[★, 2, 3, 4, 5] : 배열의 첫번째 값과 [1, 2, 3, 4, ★] : 배열의 마지막 값은 같이 붙을 수 없기 때문에

 

첫번째 값을 제거한 배열 : [2, 3, 4, 5] 과  마지막 값을 제거한 배열 : [1, 2, 3, 4] 에서의 dp[-1]값을 구하고, 이중에서 최대값을 반환하면 된다.

 

그래서 

return max(houseRobber(nums[:-1]),houseRobber(nums[1:]))

을 통해서 리턴값을 받으면 된다.

 

 

📚 참고

 

velog.io/@chelsea/1-%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming-DP

[자료구조와 알고리즘] 동적 계획법(Dynamic Programming, DP)