[LeetCode 풀이/python] 213. House Robber (medium)

문제 설명: 당신은 전문 강도범이고 거리를 따라 집을 약탈할 계획이다. 각 집에는 특정 금액이 숨겨져 있다. 이곳의 모든 집들은 원형으로 배치되어 있다. 다시 말해, 첫번째 집은 마지막 집과 이웃하고 있다. 동시에, 이웃한 집들은 연결된 방범 시스템을 갖추고 있어, 이웃한 두 집이 같은 날 밤 약탈될 경우 자동으로 경찰에 연락이 간다. 

각 집에 숨겨진 돈의 액수를 나타내는 정수 배열 nums 가 주어졌을 때, 경찰에 알려지지 않고 하룻밤에 약탈할 수 있는 가장 큰 액수의 돈을 리턴하시오.

 

(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 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.)

 

 

예시 1)

입력: nums = [2,3,2]  -->  출력: 3

설명: 첫번째 집 (money = 2) 을 약탈한 다음 세번째 집 (money = 2) 을 약탈하는 것이 불가능함. (집들이 원형으로 위치해 있으므로 첫번째 집과 세번째 집이 이웃하는 상태)

 

예시 2)

입력: nums = [1,2,3,1]  -->  출력: 4

설명: 첫번째 집 (money = 1) 을 약탈한 후 세번째 집 (money = 3) 을 약탈할 때 가장 많은 돈을 얻을 수 있으며, 총 약탈 금액은 1 + 3 = 4 임.

 

예시 3)

입력: nums = [0]  -->  출력: 0

 

제한 조건:

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

 

------ * ------ * ------ * ------

 

[풀이 1안]  (not a solution...!)

• 접근법
  • i 번째 집까지 약탈했을 때 최대로 얻을 수 있는 금액을 memoization 테이블 dp_amt[i] 에 저장함
    • dp_amt[i] 의 값은 i-2 번째 집까지 약탈한 뒤 (i-1 은 건너뛰고) 추가로 i 번째 집을 약탈하여 얻은 총 금액
    • 또는,  i-1 번째 집까지 약탈하여 얻은 금액에서 i-1 번째 집에서 얻을 수 있는 금액은 뺀 금액 (실제 i-1 번째 집을 약탈하면 i 번째 집을 약탈할 수 없으므로) + i 번째 집에서 얻은 금액
  • 하지만 첫번째 집을 약탈했을 경우 이와 동시에 마지막 집을 약탈할 수 없으므로, 별도 dp_check 를 만들어 i 번째 집까지 약탈하여 최대 금액을 얻었을 때 첫번째 집에 대한 약탈이 포함되어 있었는지를 dp_check[i] 에 저장함
    • dp_amt[i] 를 계산하는 두 가지 각 경우에 대해, 이전까지 약탈 대상에 첫번째 집이 포함되었을 경우 dp_check[i] 의 값도 따라서 업데이트 함
    • 마지막 i 번째 집을 약탈하려고 할 때, 이전까지의 최대 금액을 만드는 과정에서 첫번째 집을 약탈했었다면, 첫번째 집에서 얻은 금액을 빼주고 dp_check[i-2] / dp_check[i-1] 값도 False 로 바꿔줌

 

• 코드 구현

def rob(nums: List[int]) -> int:
    if len(nums) == 1: return nums[0]
        
    dp_amt, dp_check = [0]*len(nums), [False]*len(nums)
    dp_amt[0], dp_amt[1] = nums[0], nums[1]
    dp_check[0] = True    # first house robbed 
        
    for i in range(2, len(nums)):
        b2, b1 = dp_amt[i-2], dp_amt[i-1]-nums[i-1]
             
        if (i == len(nums)-1):
            if dp_check[i-2]: 
                b2 = b2 - nums[0]
                dp_check[i-2] = False
            if dp_check[i-1]: 
                b1 = b1 - nums[0]
                dp_check[i-1] = False
        #print(i, b2, b1)
                
        if b2 >= b1:
            dp_amt[i] = b2 + nums[i]
            dp_check[i] = dp_check[i-2]
        else:
            dp_amt[i] = b1 + nums[i]
            dp_check[i] = dp_check[i-1]
                
    #print(dp_amt)
    #print(dp_check)
    return max(dp_amt)
    

 

• 결과
  • Wrong Answer 를 갖는 케이스가 있었음
    • 마지막 집의 max amount 값을 계산하는 과정에서, b2, b1 에서 첫번째 집의 값을 빼주게 되는 경우 않는 경우 재계산된 b2 가 첫번째 집을 약탈하지 않고 얻을 수 있는 최대값이 아닌 경우가 존재함
    • 예시) nums = [2,1,2,6,1,8,10,10]  -->  Expected = 25  &  Output = 24

 

 

[풀이 2안]  (w/ solution peeping)

• 접근법
  • 풀이는 의외로 단순했다...
    • 주어진 nums 의 길이가 n 일 때, 원형 배치가 아닌 (일직선 배치) 상황을 전제하고 두 개의 dp 를 계산 & 저장하되,
    • 각각 첫번째 ~ n-1 번째 집까지의 최대 금액을 계산 & 두번째 ~ n 번째 집까지의 최대 금액을 계산
    • 두 dp 에 대해 각 dp 의 최대 값 중 큰 값을 최종 금액으로 리턴...!!

 

• 코드 구현

def rob(nums: List[int]) -> int:
    if len(nums) == 1: return nums[0]
     
    dp_1, dp_2 = robber(nums[:-1]), robber(nums[1:])
    return max(max(dp_1), max(dp_2))
    
def robber(nums):
    if len(nums) == 1: return nums
        
    dp = [0]*len(nums)
    dp[0], dp[1] = nums[0], nums[1]
        
    for i in range(2, len(nums)):
        b2, b1 = dp[i-2], dp[i-1]-nums[i-1]
        dp[i] = max(b2, b1) + nums[i]
        
    return dp
    

 

• 결과
  • 시간 복잡도 O(n) + O(n) = O(n) !