LeetCode - 집도둑 II

문제 설명

당신은 거리를 따라 집을 털려는 전문 강도입니다. 각 집에는 일정 금액의 돈이 숨겨져 있습니다. 이 곳의 모든 집은 원형으로 배열되어 있습니다. 즉, 첫 번째 집은 마지막 집의 이웃입니다. 한편, 인접한 집에는 보안 시스템이 연결되어 있어 같은 날 밤 인접한 두 집에 무단 침입이 발생하면 자동으로 경찰에 신고한다.

각 집의 금액을 나타내는 정수 배열 nums가 주어지면 **경찰에 알리지 않고** 오늘 밤에 훔칠 수 있는 최대 금액을 반환합니다.

문제 진술 출처: https://leetcode.com/problems/house-robber-ii/

예 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.

예 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.

예 3:

Input: nums = [1,2,3]
Output: 3

제약:

- 1 <= nums.length <= 100
- 0 <= nums[i] <= 1000

설명

이 문제는 이전 블로그 게시물House Robber의 확장입니다. 문제의 까다로운 부분은 집들이 원형으로 배열되어 있다는 것입니다. 첫 번째 집은 마지막 집의 이웃이므로 집 중 하나를 강탈할 수 없습니다.

여기서 두 가지 경우를 실행해야 합니다.

첫 번째 집을 선택하고 마지막 집을 무시합니다. nums[0]에서 nums[len - 2]까지 약탈할 수 있는 최대 금액을 계산합니다.

마지막 집을 선택하고 첫 번째 집을 무시합니다. nums[1]에서 nums[len - 1]까지 약탈할 수 있는 최대 금액을 계산합니다.

여기에서 알고리즘을 확인해 봅시다.

// rob(nums) method
- set n = nums.size();

// for empty array.
- if n == 0
  - return 0

// for an array of size 1
- if n == 1
  - return nums[0]

- return max(robHelper(nums, 0, n - 2), robHelper(nums, 1, n - 1))

// robHelper(nums, l, r)
- set include = 0
      exclude = 0
      tmp = 0

- loop for i = l; i <= r; i++
  - set tmp = max(include, exclude)

  - update include = exclude + nums[i]

  - set exclude = tmp

- return max(include, exclude)

C++, Golang, Javascript에서 우리의 솔루션을 확인해 봅시다.

C++ 솔루션

class Solution {
public:
    int robHelper(vector<int>& nums, int l, int r) {
        int include = 0, exclude = 0, tmp;

        for(int i = l ; i <= r ; i++) {
            tmp = max(include , exclude);
            include = exclude + nums[i];
            exclude = tmp;
        }

        return max(include , exclude);
    }

    int rob(vector<int>& nums) {
        int n = nums.size();

        if(n == 0) {
            return 0;
        }

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

       return max(robHelper(nums, 0, n - 2) , robHelper(nums, 1, n - 1));
    }
};

골랑 솔루션

func max(a, b int) int {
    if a > b {
        return a
    }

    return b
}

func robHelper(nums []int, l, r int) int {
    include, exclude, tmp := 0, 0, 0

    for i := l; i <= r; i++ {
        tmp = max(include, exclude)
        include = exclude + nums[i]
        exclude = tmp
    }

    return max(include, exclude)
}

func rob(nums []int) int {
    n := len(nums)

    if n == 0 {
        return 0
    }

    if n == 1 {
        return nums[0]
    }

    return max(robHelper(nums, 0, n - 2), robHelper(nums, 1, n - 1))
}

자바스크립트 솔루션

var robHelper = function(nums, l, r) {
    let include = 0, exclude = 0, tmp;

    for(let i = l; i <= r; i++) {
        tmp = Math.max(include, exclude);
        include = exclude + nums[i];
        exclude = tmp;
    }

    return Math.max(include, exclude);
}

var rob = function(nums) {
    let n = nums.length;

    if(n == 0) {
        return 0;
    }

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

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

주어진 입력에 대해 알고리즘을 연습해 봅시다.

Input: nums = [1, 3, 2, 6, 8, 4]

// rob(vector<int>& nums)
Step 1: n = nums.size()
          = 6

Step 2: n == 0
        6 == 0
        false

Step 3: n == 1
        6 == 1
        false

Step 4: return max(robHelper(nums, 0, n - 2), robHelper(nums, 1, n - 1))
        return max(robHelper(nums, 0, 4), robHelper(nums, 1, 5))

First call for robHelper(nums, 0, 4)
Step 5: include = 0
        exclude = 0
        tmp

Step 6: loop for i = l; i <= r
        i = 0
        0 <= 4
        true

        tmp = max(include , exclude)
            = max(0, 0)
            = 0

        include = exclude + nums[i]
                = 0 + nums[0]
                = 0 + 1
                = 1

        exclude = tmp
                = 0

        i++
        i = 1

Step 7: loop for i <= r
        1 <= 4
        true

        tmp = max(include , exclude)
            = max(1, 0)
            = 1

        include = exclude + nums[i]
                = 0 + nums[1]
                = 0 + 3
                = 3

        exclude = tmp
                = 1

        i++
        i = 2

Step 8: loop for i <= r
        2 <= 4
        true

        tmp = max(include , exclude)
            = max(3, 1)
            = 3

        include = exclude + nums[i]
                = 1 + nums[2]
                = 1 + 2
                = 3

        exclude = tmp
                = 3

        i++
        i = 3

Step 9: loop for i <= r
        3 <= 4
        true

        tmp = max(include , exclude)
            = max(3, 3)
            = 3

        include = exclude + nums[i]
                = 3 + nums[3]
                = 3 + 6
                = 9

        exclude = tmp
                = 3

        i++
        i = 4

Step 10: loop for i <= r
         4 <= 4
         true

         tmp = max(include , exclude)
             = max(9, 3)
             = 9

         include = exclude + nums[i]
                 = 3 + nums[4]
                 = 3 + 8
                 = 11

         exclude = tmp
                 = 9

         i++
         i = 5

Step 11: loop for i <= r
         5 <= 4
         false

Step 12: return max(include, exclude)
                max(11, 9)

         We return 11

// we come back to step 4 and compute robHelper(nums, 1, 5)

Step 13: return max(11, robHelper(nums, 1, 5))

call for robHelper(nums, 1, 5)
Step 14: include = 0
         exclude = 0
         tmp

Step 15: loop for i = l; i <= r
         i = 1
         1 <= 5
         true

         tmp = max(include , exclude)
             = max(0, 0)
             = 0

         include = exclude + nums[i]
                 = 0 + nums[1]
                 = 0 + 3
                 = 3

          exclude = tmp
                  = 0

          i++
          i = 2

Step 16: loop for i <= r
         i = 2
         2 <= 5
         true

         tmp = max(include , exclude)
             = max(3, 0)
             = 3

         include = exclude + nums[i]
                 = 0 + nums[2]
                 = 0 + 2
                 = 2

         exclude = tmp
                 = 3

         i++
         i = 3

Step 17: loop for i <= r
         i = 3
         3 <= 5
         true

         tmp = max(include , exclude)
             = max(2, 3)
             = 3

         include = exclude + nums[i]
                 = 3 + nums[3]
                 = 3 + 6
                 = 9

         exclude = tmp
                 = 3

         i++
         i = 4

Step 18: loop for i <= r
         i = 4
         4 <= 5
         true

         tmp = max(include , exclude)
             = max(9, 3)
             = 9

         include = exclude + nums[i]
                 = 3 + nums[4]
                 = 3 + 8
                 = 11

         exclude = tmp
                 = 9

         i++
         i = 5

Step 19: loop for i <= r
         i = 5
         5 <= 5
         true

         tmp = max(include , exclude)
             = max(11, 9)
             = 11

         include = exclude + nums[i]
                 = 9 + nums[5]
                 = 9 + 4
                 = 13

         exclude = tmp
                 = 11

         i++
         i = 6

Step 20: loop for i <= r
         i = 6
         6 <= 5
         false

We return to step 13
Step 21: return max(11, robHelper(nums, 1, 5))
         return max(11, 13)

We return the answer as 13.