[LeetCode] 55. Jump Game - Java

https://leetcode.com/problems/jump-game/

Jump Game - LeetCode

---

문제

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

---

풀이

풀이 과정

정수가 담겨있는 배열 nums가 주어지고 첫 번째 인덱스에서 시작해 각 인덱스의 값만큼 최대로 이동할 수 있다고 할 때, 마지막 인덱스에 도달할 수 있는지 판단하는 문제이다.

각 인덱스를 순회하면서 주어진 배열에서 최대로 도달할 수 있는 인덱스를 갱신해 나가며 마지막 인덱스에 도달할 수 있는지 탐색한다.

만약 현재 인덱스에서 이동할 수 있는 값이 0이고 최대 인덱스가 현재 인덱스 이하라면 다음 값이 탐색이 불가능하므로 마지막 인덱스에 도달할 수 없다. 따라서 false를 반환한다.

그렇지 않다면 최소 한 칸은 이동이 가능하므로 다음 인덱스를 탐색한다.
이 때 "최대 도달 가능 인덱스"와 "현재 인덱스 + 이동 가능 거리" 중 큰 값으로 최대 도달 가능 인덱스를 갱신한다.

int maxIndex = 0; // 최대 도착 가능한 인덱스

// 최대 도착 가능한 인덱스가 nums의 길이 이상이 될 때까지 반복
for(int i = 0; maxIndex < nums.length - 1; i++){
    // 현재 인덱스에서 이동가능 거리가 0이고
    // 최대 도착 가능한 인덱스가 현재 인덱스 이하이면
    // 끝까지 도달하는 것이 불가능하므로 false를 반환
    if(nums[i] == 0 && maxIndex <= i) return false;

    // maxDistance와 현재 인덱스에서 도달 가능한 위치 중
    // 최대값으로 maxDistance를 갱신
    maxIndex = Math.max(maxIndex, i + nums[i]);
}

최대 도달 가능 인덱스가 nums의 길이 이상이 되어 반복문이 종료되면 마지막 인덱스에 도달할 수 있는 것이므로 true를 반환한다.

---

최종 코드

class Solution {
    public boolean canJump(int[] nums) {
        int maxIndex = 0; // 최대 도착 가능한 인덱스

        // 최대 도착 가능한 인덱스가 nums의 길이 이상이 될 때까지 반복
        for(int i = 0; maxIndex < nums.length - 1; i++){
            // 현재 인덱스에서 이동가능 거리가 0이고
            // 최대 도착 가능한 인덱스가 현재 인덱스 이하이면
            // 끝까지 도달하는 것이 불가능하므로 false를 반환
            if(nums[i] == 0 && maxIndex <= i) return false;

            // maxDistance와 현재 인덱스에서 도달 가능한 위치 중
            // 최대값으로 maxDistance를 갱신
            maxIndex = Math.max(maxIndex, i + nums[i]);
        }
        // 탐색이 종료되면 최대 최대 이동 가능 거리가 nums 길이 이상이므로 true를 반환
        return true;
    }
}

---