Day009 - 55. Jump Game

55. Jump Game

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 105

내 풀이

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        start_idx = 0     # 도착지점의 index를 설정
        idx_range = 1     # 도착지점과 출발지점의 거리를 설정(기본적으로 1칸 떨어져있기 때문에 1로 초기화)
        nums = nums[::-1] # nums list를 뒤집음

        for idx in range(1, len(nums)): # 뒤집은 nums list의 index번호를 for loop을 통해 순회(0은 출발지점이기 때문에 1부터)
            if nums[idx] >= idx_range: # 확인중인 index에 해당하는 값이 해당 index와 도착지점 index간의 거리보다 크거나 같을 때 (이동 가능)
                start_idx = idx # 도착지점의 index를 현재 index로 갱신
                idx_range = 1   # 도착지점과 출발지점의 거리를 1로 초기화
            else: # 확인중인 index에 해당하는 값이 해당 index와 도착지점 index간의 거리보다 작을 때(이동 블가능)
                idx_range += 1 # 다음 index로 for loop이 넘어가고 index간의 거리를 1 추가해줌.

        # 위의 for loop을 모두 순회한 후에
        if start_idx == len(nums)-1: # 최종 도착지점의 index가 len(nums)-1과 같다면 (즉 시작지점까지 이동이 가능한 경우)
            return True # True를 return
        else: # 최종 도착지점의 index가 len(nums)-1과 같지 않다면 (즉 시작지점까지 이동이 불가능한 경우)
            return False # False를 return

이번 문제는 생각보다 어려웠기도 했고, 지금도 이게 완벽하게 맞는건지 의구심이 드는 문제였다.

코드의 각 줄마다 주석을 달아놨지만 간단하게 그림으로 설명을 해 보면,

• 우선 nums list를 뒤집는다. (그림은 뒤집지 않고 설명)
• 목표 도착 지점(start_idx = 0)에서 한 칸 앞(idx__range = 1)의 값(nums[idx])을 통해 해당 지점에서 목표 도착 지점까지 이동이 가능한지 확인.
  • 이동이 가능하다면 해당 idx를 새로운 목표 도착 지점으로 설정 후 idx_range를 1로 초기화.
  • 이동이 불가능하다면 이동이 가능한 idx를 찾을 때 까지 idx_range를 1씩 추가하며 탐색

이렇게 모든 과정을 거친 후 목표 도착 지점이 시작부분으로 갱신이 된다면 끝까지 도착이 가능하다는 로직을 통해 문제를 해결하였다.

# Time Complexity : \(O(N)\)