House Robber

LeetCode - The World's Leading Online Programming Learning Platform

문제 파악 [필수 작성]

자유 형식

문제이해

제한 조건 확인

아이디어

1차

현재 위치꺼 버리고 현재위치-1 번째 꺼 저장할래?
아니면 현재위치꺼랑 현재위치 - 2 번째꺼 합쳐서 저장할래?
그렇게 끝까지 쭉 한다음 마지막꺼 리턴

2차

현재 위치꺼 버리고 현재위치-1 번째 꺼 저장할래?
아니면 현재위치꺼랑 현재위치 - 2 번째~0번째꺼 중
가장 큰거랑 합쳐서 저장할래?
그렇게 끝까지 쭉 한다음 마지막꺼 리턴

시간복잡도

O(n^2)

자료구조

접근 방법 [필수 작성]

2차

코드 구현 [필수 작성]

1차시도

2차시도

1차시도 코드를 짜고서 시간복잡도가 O(n)인데 제한조건이 길이가 400밖에 안되는걸 의심했었어야했는데 의심하지 못했다.

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        if len(nums) == 2:
            return max(nums[0],nums[1])
        for i in range(2,len(nums)):
            nums[i] = max(nums[i]+max(nums[0:i-1]),nums[i-1])
        return nums[-1]

배우게 된 점 [필수 작성]

아래의 방식으로 구현하면 메모리를 적게 쓸 수 있다는 장점이 있다.

class Solution:
    def rob(self, nums: List[int]) -> int:
        prev, curr = 0, 0
        for num in nums:
            prev, curr = curr, max(prev+num, curr)
        return curr

질문 [ 필수 X ]

댓글로 또는 이곳에 질문 남겨주세요.