[Leetcode 아주 상세한 문제풀이] 213. House Robber II – 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 213번 문제 House Robbert II 다.

우선 문제를 살펴보자.

 

리트코드 213번 문제 House Robbert II 링크

House Robber II - LeetCode

House Robber II - LeetCode

 

 

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.

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.

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.

Example 3:
Input: nums = [1,2,3]
Output: 3
 
Constraints:
1 <= nums.length <= 100
0 <= nums[i] <= 1000

 

 

문제 설명

문제를 간략히 살펴보자. 인풋으로 정수로 이루어진 배열이 주어진다. 이때 각 index는 집을 나타내고 그 element 값은 그 집에 있는 돈의 액수를 나타낸다. 우리는 도둑으로서(?) 집들을 도둑질하고자 한다. 이때 각 집은 원형으로 서로 연결되어 있다. 인접한 두 집은 보안 시스템이 존재하는데 옆 집이 털릴경우 보안 시스템이 울리게 된다. 이 말인 즉 도둑 입장에서는 연속된 두 집을 도둑질 할 수 없다는 얘기가 된다. 이런 조건에서 도둑이 올릴 수 있는 최대 수익(?)은 얼마인지 알아내라는 문제다.

예를 들어 문제 예시 2번과 같이 [1, 2, 3, 1]라는 인풋이 주어졌다고 생각해 보자. 이 네 집은 서로 원형으로 연결되어 있다. 따라서 첫번째 집에서 1만큼 돈을 훔치면 두번째 집에서 도둑질을 할 수 없다는 얘기가 된다. 따라서 이 경우 첫번째 집과 세번째 집에서 도둑질 할 경우 총 수익(?)은 4가 되어 최대 수익이 된다. 문제를 이해하기 그리 어렵지 않으니 곧바로 문제를 풀어보도록 하자.

 

 

문제 접근법

이 문제를 해결하기 위해 우리는 dynamic programming을 이용할 것이다.

이때 한 가지 고려해야 할 사항은 모든 집들이 원형으로 위치해 있다는 것이다.

즉, 첫번째 집과 마지막 집은 서로 근접해 있다는 것이다.

따라서 첫번째 집과 마지막 집을 연속으로 도둑질 할 수 없다.

우리는 이 문제를 두 가지로 나누어 접근해야 한다.

1) 1번째 집 (index=0) 부터 시작하여 도둑질 하는 경우 (마지막 집 제외)

2) 2번째 집 (index=1) 부터 시작하여 도둑질 하는 경우 (첫번째 집 제외)

우리는 helper function을 정의해 각 경우에서 도둑질로 올릴 수 있는 최대 수익을 계산할 것이다.

그 후 두 가지 경우의 수 중 더 큰 수익을 취한다면 그것이 바로 도둑질로 올릴 수 있는 최대 수익이 된다.

이제 코드로 한 번 살펴보자.

 

 

문제 풀이

도둑질 할 집에 있는 돈의 액수 배열을 입력 받을 함수를 정의해 준다. (line 1)

우선 예외 케이스를 위해 입력받은 배열의 길이를 확인한다. (line 10)

만약 배열의 길이가 1이라면 집이 1개밖에 없다는 뜻이다. (line 11)

이 경우 그 집에서 얻을 수 있는 돈이 최대 수익이므로 그 집의 element를 리턴하고 종료한다. (line 12)

이제 각 경우에 대해 얻을 수 있는 최대 수익을 계산해 준다.

첫번째 경우 첫번째 집 부터 탐색하고 (nums[:-1]), 두번째 경우 두번째 집 부터 탐색한다. (nums[1:]).

문제의 조건에 따라 첫번째 경우 마지막 집은 제외하고 (인접해 있으므로) 두번째 경우 마지막 집을 포함한다.

앞서 설명한대로 우리는 최대 수익을 계산하는 helper function을 만들어 줄 것이다. (line 2)

이때 우리는 추가로 아래와 같은 2가지 경우를 생각해줘야 한다.

i) 두 집 전까지 도둑질 했을 때 최대 수익 (rob1)

ii) 바로 직전 집까지 도둑질 했을 때 최대 수익 (rob2)

따라서 현재 탐색하고 있는 집을 도둑질 할 경우 (수익=n) 지금까지 최대 수익은 rob1 + n 혹은 rob2가 된다.

바로 직전 집을 도둑질 할 경우 현재 탐색하고 있는 집을 도둑질 할 수 없기 때문에 rob2에는 n을 더해주지 않는다.

이 두 경우에서 더 큰 값을 취하면 그것이 현재까지 도둑질 한 최대 수익이 된다. (line 5)

다음 집 탐색을 위하여 rob1은 rob2로 업데이트 해주고 (line 6) rob2는 현재까지 최대 수익으로 업데이트 해준다. (line 7)

이 과정을 모든 집에 대하여 마치고 나면 결국 얻을 수 있는 최대 수익은 rob2에 들어가있다.

위에서 설명한대로 rob2는 바로 직전 집까지 도둑질 했을 때 최대 수익이기 때문이다.

따라지 마지막 집까지 탐색을 마치고 나면 그때의 최대 수익이 rob2에 들어있다.

따라서 rob2를 리턴해준다.

최종적으로 첫번째 집과 두번째 집에서 각각 탐색을 시작하는 경우에 대해 각각 최대 수익을 계산한다. (line 13)

그리고 그 중 더 큰 값을 리턴하고 종료한다.

 

 

문제 풀이 코드

def rob(nums):
    def rob_linear(houses):
        rob1, rob2 = 0, 0
        for n in houses:
            new_rob = max(rob1 + n, rob2)
            rob1 = rob2
            rob2 = new_rob
        return rob2
 
    n = len(nums)
    if n == 1:
        return nums[0]
    return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))
 
# Test the function with the provided examples
print(rob([2, 3, 2]))  # Output: 3
print(rob([1, 2, 3, 1]))  # Output: 4
print(rob([1, 2, 3]))  # Output: 3