55. Jump Game

https://leetcode.com/problems/jump-game/description/?envType=featured-list&envId=top-google-questions%3FenvType%3Dfeatured-list&envId=top-google-questions%3FenvType%3Ddaily-question&envId=2023-09-01

input :

• nums

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

• 마지막 위치까지의 도달가능 여부를 출력하시오.

조건 :

• 1 <= nums.length <= 10,000
• 0 <= nums[i] <= 100,000

---

Solution explain : Solution1

idea

• 이동하는 최솟값을 묻는 것이 아니다.!
• 이동 가능 여부만 확인하면 되기에 1번의 순회로 최대 이동가능 거리를 찾으면 된다.

• 1. 현재 위치가 접근이 가능한가? (can_move라는 변수를 통해서 확인)
• 2. can_move의 업데이트가 가능한가? (idx + step 과의 비교를 통해서 확인)
• 3. 이를 다 만족해서 끝까지 오면 True를 반환한다.

주의

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        flag = False
        can_move = 0
        length = len(nums)

        for idx, step in enumerate(nums):
            if idx > can_move:
                break

            if idx + step >= length:
                flag = True
                break

            can_move = max(idx + step, can_move)
            
        if can_move == length - 1:
            return True
        return flag