문제

https://leetcode.com/problems/jump-game/description/?envType=study-plan-v2&envId=top-interview-150

해결 방법

• nums = [2,3,1,1,4]인 경우
  • i = 0인 경우, 최대 2까지 갈 수 있음
  • i = 1인 경우, 현재 2까지 갈 수 있으므로 1도 갈 수 있음, 최대 4까지 갈 수 있게 됨
  • i = 2인 경우, 현재 4까지 갈 수 있으므로 2도 갈 수 있음, 2에서 점프하면 최대 3까지 갈 수 있기 때문에 기존의 최댓값 4유지
  • 위와 같이 진행 후 i가 n-1까지 진행된다면 true return
• nums = [3,2,1,0,4]인 경우
• i = 0인 경우, 0에서 점프하면 최대 3까지 갈 수 있음
• i = 1인 경우, 1에서 점프해도 최대 3까지 갈 수 있음
• i = 2인 경우, 2에서 점프해도 최대 3까지 갈 수 있음
• i = 3인 경우, 현재 3까지 갈 수 있으므로 3까지는 갈 수 있지만, 최댓값이 더 이상 증가하지 않으므로 더는 갈 수 없음 => i가 n-1까지 진행하지 못했으므로 false return

코드

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int max = 0;

        for (int i = 0 ; i < n ; i ++) {
            if (i > max) {
                return false;
            }

            if (max < i + nums[i]) {
                max = nums[i] + i;
            }
        }

        return true;
    }
}

결과