DP_LeetCode_house-robber

https://leetcode.com/problems/house-robber/submissions/

접근 방법

1. 큰 수로 정렬, 큰 수 부터 sum에 더해간다.
2. 더한 수의 index, +1, -1을 cautions에 저장하여, 접근 불가능 한 요소로 지정.
3. array의 elements 만큼 반복.
4. return sum

틀린 코드

[2,3,2]의 test case에서 return 3 을 하게 된다.

큰 수인 3을 먼저 저장한 뒤, 양쪽의 2를 접근 불가능하게 정하기 때문.

class Solution {
    func rob(_ nums: [Int]) -> Int {
        var cautions: [Int] = []
        var sum = 0
        
        let array = nums.enumerated().sorted(by: {
            $0.1 > $1.1
        })
        
        for (index, num) in array {
            if cautions.contains(index) {
                continue
            }
            
            sum += num
            cautions.append(index)
            cautions.append(index - 1)
            cautions.append(index + 1)
            
        }
        
        return sum
    }
}

정답 코드

고수의 코드를 참조,,,,

Runtime: 7 ms, faster than 17.13% of Swift online submissions for House Robber.

Memory Usage: 13.9 MB, less than 81.48% of Swift online submissions for House Robber.

import Foundation

class Solution {
    func rob(_ nums: [Int]) -> Int {
        var array = nums
        
        if array.count < 3 {
            return nums.max()!
        }
        
        array[2] += array[0]
        
        for i in 3..<array.count {
            array[i] += max(array[i-2], array[i-3])
        }
        
        return array.max() ?? 0
    }
}