[LeetCode] 55. Jump Game

Problem

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 <= 10^4
• 0 <= nums[i] <= 10^5

---

Solution

class Solution {
    public boolean canJump(int[] nums) {
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            if (max < i)
                return false;
            max = Math.max(nums[i] + i, max);
        } return true;
    }
}

Explanation

• n번째 요소로 점프하기 위해서는 1 ~ n-1번째 요소 중 하나의 요소에서, 인덱스와 요소의 값의 합이 n이상이 되는 요소가 존재해야 한다.
• 1 ~ n-1번째 각요소에서 인덱스와 요소의 값의 가장 큰 합만 알게되면 n번째 요소로 점프 할 수 있는지 알수있다. 이 값을 할당하기 위해 변수 max를 선언한다.
• 변수 max의 값은 해당 요소 이전 요소 중 가장 멀리 점프할 수 있는 값을 의미한다.

  int max = 0;
  

• 각 요소로 점프할 수 있는지 확인하기 위해 for 반복문을 선언한다.
• 변수 max의 값이 인덱스보다 작다면 해당 인덱스를 가진 요소로 점프하지 못한다는 것을 의미하므로 false를 반환하도록 한다.
• 그리고 각 요소의 인덱스를 지나갈 때마다 점프할 수 있는 가장 긴 거리를 찾아 변수 max에 할당해준다.

  for (int i = 0; i < nums.length; i++) {
    if (max < i)
        return false;
    max = Math.max(nums[i] + i, max);
  }
  

• for 반복문을 전부 진행했으면 배열 nums의 마지막 요소까지 점프할 수 있다는 의미이므로 true를 반환한다.

  return true;