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

Example 2:
Input: nums = [3,2,1,0,4]
Output: false

Constraints:
1 <= nums.length <= 10^4
0 <= nums[i] <= 10^5

첫번째 인덱스에서 시작으로 배열의 각 요소는 해당 위치에서 얼만큼 갈 수 있는지를 나타낸다.

마지막 인덱스에 도달할 수 있으면 true, 아니면 false 를 반환한다.

---

풀이

각 index에서는 어디까지 점프할 수 있는지 확인해보자

 

예제 1:

• 0 -> 1, 2
• 1 -> 2, 3, 4
• 2 -> 3
• 3 -> 4

예제 2:

• 0 -> 1, 2, 3
• 1 -> 2, 3
• 2 -> 3
• 3 -> 3

이렇게 4번 index까지 도달할 수 있는지 찾으면 되는 문제인데,

위와 같은 방법으로 접근을 한다면 수행시간이 오래걸릴 것이다.

 

예제 1번의 0번 index를 보면, 1, 2번까지만 도달하기 때문에, 1, 2번 index에서 또 어디까지 도달할 수 있을지 찾아야한다.

위의 예제에서는 경우의 수가 별로 없지만 제약조건인 0 <= nums[i] <= 10^5 을 확인해보면 수행시간을 신경쓰게된다.

 

O(n)의 수행시간으로 만들기 위해 반대로 접근할 수 있겠다.

예제1:
[2,3,1,1,4] 3번 index는 4번 index에 접근할 수 있다.
[2,3,1,1,4] 2번 index는 3번 index에 접근할 수 있다.
[2,3,1,1,4] 1번 index는 2번 index에 접근할 수 있다.
[2,3,1,1,4] 0번 index는 1번 index에 접근할 수 있다.

예제 2:
[3,2,1,0,4] 3번 index는 4번 index에 접근할 수 없다.
[3,2,1,0,4] 2번 index는 4번 index에 접근할 수 없다.
[3,2,1,0,4] 1번 index는 4번 index에 접근할 수 없다.
[3,2,1,0,4] 0번 index는 4번 index에 접근할 수 없다.

 

위의 풀이법으로 코드를 작성해보자.

// 접근해야할 index를 지정한다.
// 최초 index는 길이의 끝
int index = nums.length - 1;

// 접근해야할 index 이전 index에서 접근이 가능한지 확인한다.
// 현재 index에서 nums[index] 을 더해 접근해야할 index보다 값이 커야한다.
if (nums[prevIndex] + prevIndex >= index) {
	index = prevIndex; // 접근 가능하다면 다음에는 그 index에 접근 가능하면된다.
}

// 0 index까지 접근 가능했다면 결과는 true이다.
return index == 0;

---

결과

class Solution {
    public boolean canJump(int[] nums) {
        int index = nums.length - 1;
        for (int i = index; i >= 0; i--) {
            if (nums[i] + i >= index) {
                index = i;
            }
        }
        return index == 0;
    }
}