리트코드 - 198. House Robber

리트코드 - 198. House Robber

출처 - https://leetcode.com/problems/house-robber/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

당신은 길거리의 집들을 훔칠 계획을 세운 전문적인 도둑입니다. 집집마다 특정 금액의 돈이 숨겨져 있으며, 훔치는 것을 멈출 유일한 제약조건은 인접한 집들의 보안 시스템이 연결되어 자동으로 경찰에 연락이 되는 것이고, 이러한 연락은 인접한 두 집이 같은 날 저녁에 털린다면 발생합니다.

각 집의 돈의 양을 나타내는 정수 배열 nums가 주어지면 경찰에 경고를 주지 않고 오늘 밤 강탈할 수 있는 최대 금액을 반환하십시오.

 

의사코드

if (nums.length == 0)     0 리턴 dp = new int[nums.length] dp[0] = nums[0] if (nums.length >= 2)     dp[1] = max(nums[0], nums[1]) 반복문 시작 (i = 2부터 nums.length 전까지)     dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]) 반복문 종료 dp[nums.length - 1] 리턴

 

풀이코드

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

        int[] dp = new int[nums.length];
        dp[0] = nums[0];

        if (nums.length >= 2) {
            dp[1] = Math.max(nums[0], nums[1]);
        }

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

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

 

코드설명

연속되지 않은 수를 선택하여 최댓값을 구하는 문제로, DP를 이용해서 풀었다.

DP 배열에는 해당 배열까지의 최댓값을 저장하고자 한다.

 

먼저 첫번째 배열의 최댓값은 첫번째 배열 그 자체이므로 원래 배열값을 넣어준다.

두번째 배열은 둘 중 하나를 비교해서 큰 값을 넣어준다.

 

이후 배열부터는 '전 배열의 합'과 '전전배열의 합 + 해당 배열의 값'중 큰 값을 비교하여 저장한다.

이웃하는 값을 더하면 안되는 조건이 있기 때문에 전 배열의 합을 선택했으면 현재 배열값을 추가로 저장할 수가 없기 때문이다.

 

이렇게 만들어진 dp 배열의 마지막 값을 리턴하면 최댓값이 나오게 된다.

 

시간복잡도 - O(n)

공간복잡도 - O(n)

 

문제를 풀며 생각한 흐름과 배운 점

확실히 이제 easy를 모두 다 풀고나니 medium부터는 생각하고 접근해야 되는 문제가 많아졌다.

DP 계열 문제가 항상 생각하기가 어려웠기 때문에 이를 해결해보고 싶어서 150제중 DP계열 medium 문제를 다 풀어보고자 한다.

 

초기 코드

class Solution {
    public int rob(int[] nums) {
        if (nums.length < 3) {
            return Arrays.stream(nums).max().getAsInt();
        }

        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = nums[1];
        dp[2] = nums[0] + nums[2];

        for (int i = 3; i < nums.length; i++) {
            int maxSum = Math.max(dp[i - 3], dp[i -  2]);
            dp[i] = maxSum + nums[i];
        }
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < dp.length; i++) {
            if (max < dp[i]) {
                max = dp[i];
            }
        }

        return max;
    }
}

아직은 dp 배열이 익숙치 않다보니 초기에는 상당히 하드코딩 해버렸다.

 

로직은 다음과 같다.

1. dp배열 첫번째는 nums 배열의 첫번째를 저장
2. dp배열 두번째는 nums 배열 두번째를 저장
3. dp배열 세번째는 nums 배열 첫번째 값 + 세번째 값 저장
4. 이후 i값 부터는 바로 전전 값과 전전전 값을 비교하여 큰 값과 nums배열의 i번째 값을 더함
5. dp배열 순회하여 max값 리턴

 

이 코드가 다소 지저분한 이유는 세번째 저장까지와 이후의 로직이 일관되어 있지 않기 때문이다.

그리고 dp를 다시 순회하는 것도 중복으로 생각이 든다.

 

리팩토링

// 풀이코드와 상동

nums.length < 3 분기를 없애면서 로직을 다소 개선하여 코드를 리팩토링하였다.

 

1. nums.length가 2 이상일때만 분기를 타게 하기

2. dp가 스스로 최대값을 선택

 

다른 코드

class Solution {
    public int rob(int[] nums) {
        int[] dp = new int[nums.length + 1];
        Arrays.fill(dp, -1);
        return solve(0, nums, dp);
    }

    public static int solve(int i, int[] nums, int dp[]) {
        if (i >= nums.length) {
            return 0;
        }
        if (dp[i] != -1) {
            return dp[i];
        }
        int left = 0;
        int right = 0;
        if (i < nums.length) {
            left = nums[i] + solve(i + 2, nums, dp);
        }
        if (i + 1 < nums.length) {
            right = nums[i + 1] + solve(i + 3, nums, dp);
        }
        return dp[i] = Math.max(left, right);
    }
}

많은 dp 풀이를 보면 -1로 초기화 하는 것 같은데 이것이 값이 정해지지 않았다는 일종의 규칙같은 것 같다.

이 코드는 하향식이다. 상위 문제를 해결하기 위해 하위로 파고드는 구조로 되어 있다.

 

left와 right가 뭘 뜻하는지 다소 난해하지만 홀수번째와 짝수번째 라고 이해를 했고,

dp[1]이 항상 -1이 되는 부분또한 거슬리지만 다른 사람의 코드를 이해하려고 노력했다.

 

if분기로 인덱스를 벗어나지 않게 하는 점, dp[i] != -1 로 메모이제이션을 하는 점, return문에서 직접 대입하는 이러한 스킬을 배워둘만한 것 같다.

 

정리

배열의 값을 더할 때 DP를 이용하는 방법