[NeetCode-LeetCode] House Robber II JAVA

반응형

728x90

[NeetCode-LeetCode] House Robber II - Medium

---

접근

• dp

---

풀이

바로 전에 풀었던 집 터는 문제 2편이다. 연속된 집을 털 수 없는 규칙은 동일하나 이번엔 집이 원형으로 이루어져 있다는 점이다. 전 문제는 집이 직선 형태로 이루어져 있기 때문에 연속된 집만 털지 않고 처음부터 끝까지 진행하면 되었으나 이번에는 원형으로 첫 집과 마지막집이 연결되어 있기 때문에 해당 부분을 고려해야 한다. 

 

원형으로 집이 연결되어 있다지만 첫 번째 집과 마지막 집만 연결되어 있는 거 기 때문에 특별히 추가로 신경 쓸 내용은 많지 않다. 첫 번째 집을 턴다면 마지막 집을 털지 않으면 되는 것이고 마지막 집을 턴다면 첫 번째 집을 털지 않으면 되는 것이기 때문이다. 이렇게 두 가지 케이스로 나눠서 이 전의 코드를 그대로 수행해 준 뒤 더 큰 값을 결과로 사용하면 된다. 

    public int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        if (nums.length == 1) {
            return nums[0];
        }

        int result1 = rob(nums, 0, nums.length - 1);
        int result2 = rob(nums, 1, nums.length);

        return Math.max(result1, result2);
    }

rob 함수를 오버로딩해 실제 로직 처리하는 부분을 구현했다. 결과 1은 첫 번째 집을 털고 마지막 집을 털지 않는 경우 그리고 결과 2는 첫 집을 털지 않고 마지막 집을 터는 경우이다. 범위를 제한해서 강제로 둘 중의 하나의 집만 털도록 하는 것이다. 

    public int rob(int[] arr, int start, int end) {
        int[] nums = Arrays.copyOfRange(arr, start, end);
        
        if (nums.length == 0) {
            return 0;
        }

        if (nums.length == 1) {
            return nums[0];
        }
        
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(nums[i] + dp[i - 2], dp[i - 1]);
        }

        return dp[nums.length - 1];
    }

수행되는 처리는 이전 문제의 코드와 동일하다. 나눠진 범위를 통해 dp를 수행하여 결과를 구하고 반환한다. 

---

전체 코드

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

        if (nums.length == 1) {
            return nums[0];
        }

        int result1 = rob(nums, 0, nums.length - 1);
        int result2 = rob(nums, 1, nums.length);

        return Math.max(result1, result2);
    }

    public int rob(int[] arr, int start, int end) {
        int[] nums = Arrays.copyOfRange(arr, start, end);
        
        if (nums.length == 0) {
            return 0;
        }

        if (nums.length == 1) {
            return nums[0];
        }
        
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(nums[i] + dp[i - 2], dp[i - 1]);
        }

        return dp[nums.length - 1];
    }
}