[LeetCode | Python] 55. Jump Game

느낀점

해당 문제를 어떻게 더 쉽게 풀 수 있을까 고민하다가 결국에는 더 복잡해졌는데, 이럴 때는 사고를 조금 일반화하는 연습이 필요할 것 같다.

문제

 

https://leetcode.com/problems/jump-game/description

 

주어진 숫자 배열 nums에서, 배열의 첫 번째 인덱스에서 시작하여 각 요소의 값만큼 점프할 수 있을 때, 마지막 인덱스에 도달할 수 있는지 여부를 반환하는 문제입니다.

풀이

뒤에서부터 도달 가능한 최대 인덱스를 추적하는 방법(그리디)으로 풀었다. 도달하지 못한 경우 False, 도달한 경우 True.

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

 

결과

• 공간복잡도: $$ O(1) $$
• 시간복잡도: $$ O(1) $$