[LeetCode] 213. House Robber II

😎풀이

1. 한 집만 존재하면 반드시 털어야 함
2. 원형이므로 첫 집과 마지막 집을 털 경우 두가지를 생각
3. 도둑질은 두 경우의 수를 갖음
   3-1. 전 집을 털자
   3-2. 현재 집을 털자
4. 첫 집을 털은 최댓값과 마지막 집을 털은 최댓값 비교
5. 최댓값 출력

function rob(nums: number[]): number {
    // 한 집만 있으면 반드시 그 집 털기
    if(nums.length === 1) return nums[0]

    // 원형으로 이어져있으므로, 첫 집을 털면 마지막 집을 못 텀
    // 첫 집을 털 때
    const includeFirst = nums.slice(0, nums.length - 1)
    // 마지막 집을 털 때
    const includeLast = nums.slice(1)
    // 도둑질
    function robbing(houses: number[]) {
        // 현재 최고가
        let prevMax = 0
        // 이전 최고가
        let doublePrevMax = 0
        for(const house of houses) {
            let temp = prevMax
            // 현재 집 털기, 안 털기 중 최댓값
            prevMax = Math.max(doublePrevMax + house, prevMax)
            // 전전 최댓값은 전 최댓값으로 갱신
            doublePrevMax = temp
        }
        return prevMax
    }

    // 첫 집부터 털은 금액과, 마지막 집을 털은 금액 비교해서 최댓값으로 반환
    return Math.max(robbing(includeFirst), robbing(includeLast))
};