Leetcode 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.

당신이 그 위치에서 점프할수 있는 최대의 길이의 정보를 가지는 배열이 주어집니다.
첫번째 위치에서 마지막 위치까지 점프로 이동할수 있는지의 여부를 리턴하세요.

예시

Input: nums = [2,3,1,1,4]
Output: true
Explanation: 0번에서 1번으로 점프 > 1번에서 마지막까지 점프

제한

• $0 <= nums.length <= 10^4$
• $0 <= nums[i] <= 10^5$

풀이

문제를 처음 봤을때는 처음부터 하나하나씩 확인해 갈수 있는 위치를 찾아보는게 어떨까 했으나, 그럴 경우 시간이 너무 든다.
다시 생각해보니 뒤에서부터 찾아보면 어떨까라는 생각이 들었는데, 이를 통해 제안한 방법은 아래와 같다.

자세한 설명

1. 가장 뒤에 있는 index의 바로 왼쪽부터 왼쪽으로 계속 탐색한다.
   1-1. 만약 그 안에 있는 값이 index와의 거리보다 크거나 같으면 이동할수 있다고 판단하고 기준점을 그곳으로 옮긴다.
   1-2. 만약 1-1에 부합하는 index를 찾지 못했다면 끝까지 이동할수 없는것이다.
2. 최종적으로 index가 0에 도달하면 0번 index에서 끝 index까지 이동할수 있는 것이다.

• 이 방식을 이용한다면 맨 끝 index부터 첫 index까지 순차탐색해 O(n) 의 시간복잡도로 이 문제를 해결할수 있다.

class Solution:
    def findJump(self, nums: List[int], point: int) -> int:
        source = point - 1
        while source >= 0:
            distance = point - source
            if nums[source] >= distance: return source
            source -= 1
        return -1
    def canJump(self, nums: List[int]) -> bool:
        start = len(nums)-1
        while start != 0:
            start = self.findJump(nums, start)
            if start == -1: return False
        return True