55. Jump Game

배열 안의 숫자는 이동할 수 있는 거리를 뜻한다. 칸을 이동하면서 마지막 인덱스에 위치할 수 있는지를 검사하는 문제다.

Solution

DP 를 사용해서 풀었다.
배열을 돌면서 최대 이동 거리를 이동하면서 마지막 인덱스 위치에 도달할 수 있는지를 판별한다.
1. 0번째 숫자를 초기 점프 거리로 저장한다.
2. 배열을 돌면서 최대 이동 거리를 갱신하고 마지막 인덱스 위치에 도달할 수 있는지를 판별한다.
3. 현재 인덱스 i가 jump(최대 점프 거리)보다 크다면 도달할 수 없는 위치이므로 False를 반환한다.

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        if len(nums) == 1: return True

        jump = nums[0]
        for i, num in enumerate(nums): # 인덱스와 값 꺼내기 O(n)
            if i > jump: return False # 현재 인덱스가 점프 거리보다 길다 : 도달할 수 없음
            jump = max(jump, i + num) # 최대 이동 거리 갱신
            if jump >= len(nums) - 1: return True # 마지막 인덱스 위치에 도달할 수 있는지 검사
        return True

시간 복잡도

결국은 배열을 다 돌기 때문에 O(n) 이다.