문제링크: https://leetcode.com/problems/house-robber-ii/
nums
의 각 값은 집의 돈을 의미하고 훔치는 집은 연속해서 훔칠 수 없다. 집은 원형으로 이어져있어 첫번째 집과 마지막 집이 붙어있다.(하나만 훔칠 수 있다.)
이미 House Robber I 에서 DP를 통해 집이 이어져 있지 않은 경우를 해결했다. 이번 문제도 간단히 조건을 추가한다면 I의 방식으로 풀 수 있다.
1. 첫번째 집을 훔치지 않을 경우: 두번째 ~ 마지막집을 I의 방식으로 푼다.
2. 마지막 집을 훔치지 않을 경우: 첫번째 ~ 마지막에서 두번째 집을 I의 방식으로 푼다.
slice
)getMaxMoney
함수는 결과 arr
를 만들고 iteration을 통해 훔칠 수 있는 최대 양을 구한다.result[i]는 i번째 집을 포함해 훔친 최대 금액
result [i] = Math.max(result[i - 3], result[i - 2])
getMaxMoney
함수에 넣고 둘 중 큰 답을 반환한다.var rob = function(nums) {
// 2가지종류 1. 첫번째 집 rob => 마지막 집은 제거 2. 두번째 집 rob => 마지막 집 포함
// 1: [1 ~ end] 2: [0 ~ end - 1]
// include nums[i] and maximum
const getMaxMoney = (newNums) => {
if (newNums.length === 1) return newNums[0];
const result = new Array(newNums.length);
result[0] = newNums[0];
result[1] = newNums[1];
for (let i = 2; i < result.length; i++) {
result[i] = Math.max(result[i - 2], i > 2 ? result[i - 3] : null) + newNums[i];
}
return Math.max(result[result.length - 2], result[result.length - 1]);
}
if (nums.length === 1) return nums[0];
return Math.max(getMaxMoney(nums.slice(1)), getMaxMoney(nums.slice(0, nums.length - 1)));
};
이해하기 쉽도록 두개의 동작을 분리했지만 result
배열을 두 개 만들고 iteration
을 통해 해결할 수도 있다. slice
대신 index
를 넘기는 방식으로도 풀 수 있다. slice
는 O(n)
의 추가적인 공간과 시간을 사용한다.