[75 LeetCode] 41 - House Robber 2

[75 LeetCode]는 코딩테스트 연습을 위해 한 페이스북 개발자가 추천하는 75가지 알고리즘 문제를 풀어보는 시리즈이다.

블라인드 원문:
https://www.teamblind.com/post/New-Year-Gift---Curated-List-of-Top-75-LeetCode-Questions-to-Save-Your-Time-OaM1orEU

문제 링크: https://leetcode.com/problems/house-robber-ii/description/

House Robber II - LeetCode

 

기존 house robber와 거의 같으나, 원순열이라는 점만 다르다.

즉 같은 조건에 맨 첫 집과 마지막 집이 인접해있다는 것이다.

이를 어떻게 체크해줄까 고민하다가, 그냥 house robber의 솔루션을 fn이라 할 때
MAX(fn(0, n - 1), fn(1, n))해주는게 간단하겠다고 생각해서 그렇게 구현했다.

속도도 준수하게 나왔다.

var rob = function(nums) {
    if (nums.length === 1 || nums.length === 2) return Math.max(...nums);

    const fn = (nums) => {
        let pprev = 0;
        let prev = nums[0];
        let cur = 0;

        for(let i = 1; i < nums.length; i++ ) {
            cur = Math.max(pprev + nums[i], prev);

            pprev = prev;
            prev = cur;
        }
        return cur;
    }

    return Math.max(fn(nums.slice(1)), fn(nums.slice(0, nums.length - 1)));
};