[4코3파] #280. Leetcode 213. House Robber II

[4코3파] 1명의 스위프트 개발자가 도망가고 4명의 코틀린 개발자, 3명의 파이썬 개발자의 코딩 테스트 스터디 : 4코3파

START :

[3코1파] 2023.01.04~ (280일차)
[4코1파] 2023.01.13~ (272일차)
[4코3파] 2023.10.01 ~ (10일차)

Today :

2023.10.10 [280일차]

213. House Robber II

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

문제 설명

정수를 원소로 하는 배열이 주어질 때, 각 배열의 원소를 하나의 집이라 가정하고, 그 원소의 값은 각 집이 소유하고 있는 돈의 양이다. 여기서 주어지는 배열의 원소를 집이라고 가정하고, 모든 집은 원형으로 배열되어 있어서 첫 번째 집은 마지막 집과의 이웃이라는 의미를 가지고, 바로 옆의 인접한 집은 보안 시스템이 연결되어 있어 인접한 두 집을 털지 못하는 룰을 가질 때, 최대한 훔칠 수 있는 돈의 양을 반환함

문제 풀이 방법

198번의 house robber 에서 조금 변형된 문제로, 198 번의 house robber의 집들은 일열로 되어 있어, 첫 번째 집은 바로 오른쪽, 마지막 집은 왼쪽 배열의 집만 신경써면 됐는데, 이번에는 원형이기 때문에 첫 번째 집과 마지막 집이 이웃이므로 이를 잘 생각하고 풀어야 하는 도둑질 문제다.

198번의 house robber 문제를 하나의 함수로 두고, main solution에서 가장 첫번째 인덱스를 제외하고 나머지 배열에서의 훔칠 수 있는 돈과, 가장 마지막 인덱스를 제외한 배열에서 훔칠 수 있는 돈, 그리고 가장 첫번째 집만 털었을 때의 max 값을 비교해서 return 한다.

내 코드

class Solution:
    def rob(self, nums: List[int]) -> int:
        return max(nums[0], self.helper(nums[1:]), self.helper(nums[:-1]))

    def helper(self, nums):
        rob1, rob2 = 0,0
        for n in nums:
            tmp = max(n+rob1, rob2)
            rob1= rob2
            rob2 = tmp
        return rob2

증빙

여담

코테로 집털기 완