213. House Robber II

문제

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

Solution

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if(n==1) return nums[0];

        return Math.max(getMaxRob(nums,0, n-1), getMaxRob(nums,1,n));
    }


    public int getMaxRob(int[] nums, int start, int end) {
        int maxRob = 0;
        int preRob = 0;

        for(int i=start;i<end;i++) {
            int curVal = nums[i];
            int temp = Math.max(maxRob, curVal + preRob);
            preRob = maxRob; 
            maxRob = temp;
        }

        return maxRob;
    }
}

회고

House Robber 문제는 "각 집에는 일정 금액의 돈이 있으며, 인접한 집은 동시에 털 수 없다"는 조건을 만족하면서 최대 금액을 얻는 문제입니다. 여기에 House Robber 2에서는 "처음과 마지막 집이 인접하다"는 조건이 추가되었습니다. 즉, 집들이 원형으로 배열되어 있으므로 처음과 마지막 집을 동시에 털 수 없습니다.

 

원형 구조를 처리하기 위해:

• [0, n-1] 범위의 집들만 고려한 경우
• [1, n] 범위의 집들만 고려한 경우 두 가지로 나누어 getMaxRob 메서드를 호출하고, 최댓값을 반환합니다.

 

dp 배열을 사용하지 않고, 대신 현재 값(maxRob), 이전 값(preRob), 그리고 현재 집의 금액(curVal)을 활용하여 문제를 해결했습니다.이를 통해 공간 복잡도를 O(n)에서 O(1)로 최적화할 수 있습니다.

for(int i=start;i<end;i++) {
            int curVal = nums[i];
            int temp = Math.max(maxRob, curVal + preRob);
            preRob = maxRob; 
            maxRob = temp;
        }

• curVal: 현재 집의 금액
• maxRob: 현재 집까지 털었을 때의 최대 금액
• preRob: 바로 이전 집까지 털었을 때의 최대 금액