[LeetCode] 213. House Robber II

문제

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

House Robber II - LeetCode

———————————————————————————

 

잠깐만

이 문제에선 첫번째 집에 대한 도둑질 여부가 중요해보이네요.

아주 잘 생각해보면 198. House Robber 문제의 코드를 재활용할 수 있겠는데요???

먼저 문제 풀고 오세요.

https://skillist.tistory.com/325

[LeetCode] 198. House Robber

 

———————————————————————————

 

코드

class Solution {
    func rob(_ nums: [Int]) -> Int {
        var maxResult = 0
        var maxSums: [Int] = Array(repeating: 0, count: nums.count)
    	
        //첫번째 집을 포함하고, 마지막 집을 제외했을 경우
        for index in 0..<nums.count-1 {
            let indexFrom2 = index - 2 
            if indexFrom2 >= 0 {
                maxSums[index] = maxSums[indexFrom2]
            }
        
            let indexFrom3 = index - 3
            if indexFrom3 >= 0 {
                maxSums[index] = max(maxSums[index], maxSums[indexFrom3]) 
            }
            maxSums[index] += nums[index]
            maxResult = max(maxResult, maxSums[index])
        }
    
    	//첫번째 집을 제외하고, 마지막 집을 포함했을 경우
        maxSums = Array(repeating: 0, count: nums.count)
        for index in 0..<nums.count {
            let indexFrom2 = index - 2 
            if indexFrom2 >= 1 {
                maxSums[index] = maxSums[indexFrom2]
            }
        
            let indexFrom3 = index - 3
            if indexFrom3 >= 1 {
                maxSums[index] = max(maxSums[index], maxSums[indexFrom3]) 
            }
            maxSums[index] += nums[index]
            maxResult = max(maxResult, maxSums[index])
        }
        return maxResult       
    }
}

———————————————————————————

 

설명

핵심은 다음이에요.

첫번째 집을 포함하여 계산한 경우 마지막 집을 계산하면 안됩니다.

맞죠?

첫번째 집을 포함하지 않았으면(두번째 집부터 계산한 경우), 마지막 집을 계산해도 되죠?

맞죠?

 

코드에도 주석을 추가했지만, 범위를 변경하여

첫번째 집을 포함할 경우에는 마지막 집을 제외하여 sum을 계산합니다.

첫번째 집을 제외할 경우에는 마지막 집을 포함하여 sum을 계산합니다.

 

———————————————————————————

 

회고

어젯 밤에 "198. House Robber" 문제를 풀고, 이 문제를 봤을땐, 쉽게 풀수 있을것 같았어요.

하지만 생각을 해보니, 써클 형태이기에, 첫번째 집을 계산(루팡)했을때, 마지막 집을 계산(루팡)하면 안되는 제약조건 구현이 어렵더라구요.

그래서 잠을 자고 다음날(오늘 아침)생각을 해봤죠.

역시나 생각이 안나다가, 문뜩 2개의 로직으로 쪼개보자 라는 발상으로부터 문제를 풀수 있었습니다.

- 첫번째 집을 포함하고, 마지막 집을 제외했을 경우

- 첫번째 집을 제외하고, 마지막 집을 포함했을 경우

 

코드를 잘 보면, "198. House Robber"의 코드와 동일한것을 알 수 있습니다. 단지, 범위가 달라졌을뿐이에요.

오랜만에 문제풀면서 기분이 좋았네요.

코드 정리나 최적화를 할 수 도 있겠지만,

나중에 이 글을 다시 읽었을때, 감정을 다시 느낄수 있도록

문제풀이에 성공한 첫번째 코드로 작성해놨습니다.