[LeetCode] 55. Jump Game

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

Jump Game - LeetCode

설명

첫번째로 시도한 방법은 dfs로 탐색하는 것이었다. -> 하지만 이 경우에 시간초과가 발생한다!

 

방법은 그리디...

각 지점에 도착했을 때 가장 점프를 많이 해서 도착할 수 있는 지점을 확인한다.

최대로 이동한 것을 end라고 이름하고, end가 배열 마지막 인덱스보다 크거나 같다면 마지막 인덱스에 도착한 것이므로 true를 반환한다.

만약 end가 반복문의 i(인덱스)와 같다면, 최대로 이동할 수 있는 지점에 도착한 것이므로 false를 반환한다.

 

 

코드

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

        for(int i = 0; i < N; i++) {
            int step = nums[i];
            end = Math.max(i + step, end);

            if(end >= N-1) {
                return true;
            }
            else if(end == i) return false;
        }
        
        return true;
    }
}