[ Top Interview 150 ] 55. Jump Game

문제

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.

• 상황 : 현재 위치 (index = 0)에서 시작해서 끝까지 (index = nums.length - 1)도달할 수 있는가?
• Input : 현재 위치에서 이동할 수 있는 최대 칸 nums
• Output : 이동 가능 여부

기본 전략

• 맨 앞에서부터 계산해 나갈 경우에는 과정이 매우 복잡해진다.

  • 예를 들어 처음에 이동할 수 있는 칸이 5이라고 해보자. 이는 처음에 5칸 이동했을 때 끝까지 도달이 안된다고 해서 4, 3, 2, 1칸 이동했을 때 안된다는 보장이 없다. 그래서 각 경우마다 전부 생각해 보아야 한다.
  • 따라서 도달할 수 있는 방법이 단 한가지라고 있는 경우, 그 경우를 무조건 찾을 수 있는 방법이 필요하다.

• 뒤에서부터 하나씩 생각해보는 것이 매우 유리하다.

  • 아래 예시에서 뒤에서 2번째 원소 2를 보자. 문제의 구조 상 다다음 칸으로 갈 수 있다면 무조간 다음 칸으로 갈 수 있다는 것이 보장되어 있다.
  • 그래서 뒤에서부터 고려하여 도달할 수 있는 위치의 checkPoint를 계속 설정하고 그 다음 칸에서 해당 checkPoint에 도달할 수 있는지 여부만 계속 판단한다면 도달 여부를 쉽게 판단할 수 있다
  • 

문제 풀이 전략 (수도 코드)

• curDistance를 설정 (현재 위치에서 체크포인트까지의 거리를 의미)
• nums를 뒤에서부터 순회하면서
  • nums[i]의 값이 curDistance보다 큰 경우 (체크포인트에 도달할 수 있는 경우), curDistance의 값을 초기화 (현 위치가 체크포인트가 되고 체크포인트까지의 거리가 0로 줄었기 때문에)
  • 각 순회마다 curDistance 값을 1 증가 (이동할 때마다 체크포인트 까지의 거리가 늘어남
• 최종적으로 맨 처음 위치가 체크 포인트가 되었는지 판단함

1차 제출

class Solution {
    public boolean canJump(int[] nums) {
        int curDistance = 1;

        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] >= curDistance) {
                curDistance = 0;
            }
            curDistance++;
        }
        
        return curDistance == 1;
    }
}