LeetCode - Jump Game II

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

Jump Game II - LeetCode

 

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
    let cnt = 0;
    let index = 0;
    let dest = nums.length-1;
    while(index< dest){
        let a= nums[index];
         if(index+a>=dest){
            return cnt+1;
        }
        let rest = nums.slice(index+1, index+1+a);
        let max = a; 
        let maxindex= rest.length-1;
        for(let i = 0 ; i < rest.length ; i++){
            if(i+1+rest[i]>max){
                max = i+1+rest[i];
                maxindex = i;
            }
        }
        index+= maxindex+1;
        cnt++
    }
    return cnt;
};

1. 현재 목적지에 도달할수 있는지 확인

2. 나머지 중에서 index와 값의 합이 제일 큰 애를 골라서 움직임(제일 멀리 가는 것을 고르는 것임)

3. 반복

 

 

처음엔 단순 값이 제일 큰 것을 골랐었는데,

 

다음 index를 택할 배열이 [6, 5, 1, 1, 1, 1, 1, 1, 1, 1,]

 

이런식으로 있다면 index 0의 6보다 마지막 index의 1이 더 멀리 가기 떄문!