[Coding Test] LeetCode - 198. House Robber

Leet Code 198. House Robber(https://leetcode.com/problems/house-robber/)를 풀고 문제를 푼 기록이다. 언어는 JS를 사용하였다.

198. House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems 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 = [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 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

풀이

DP Study Plan을 풀기 시작한지 3일이 지났는데 이제 Medium 난이도를 풀기 시작하였다. 이 문제는 여태까지 풀어왔던 문제보다 약간 꼬아서낸 문제였다.

기존에 풀어왔던 문제는 조건이 n-1 또는 n-2 값을 합산하는 형태였다면 이번 문제는 n-1을 제외한 값중에 가장 큰값을 찾아서 더해주는 문제였다.

var rob = function(nums) {
    const arr = [nums[0]];
  
    for (let i = 1; i <= nums.length -1; i += 1) {
      arr[i] = i === 1 ? nums[i] : Math.max(...arr.slice(0, i-1) ) + nums[i];
    }
  
    return Math.max(...arr);
};

코드를 보면 i === 1 인 경우를 조건처리했는데, arr.slice()를 할 때 i가 0이면 -infinity 값이 나오기 때문에 이렇게 처리하였다.

결과

Runtime: 83 ms, faster than 70.16% of JavaScript online submissions for House Robber.

Memory Usage: 42.1 MB, less than 43.50% of JavaScript online submissions for House Robber.