55. Jump Game

문제

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

 

풀이

해당 문제는 두 가지 방식으로 풀이해봤다.

하나는 각 칸마다 도달할 수 있는 경우를 기록하는 방법, 또 다른 방법은 마지막 인덱스 부터 도달할 수 있는지 검증하는 방법이다.

 

코드

/**
 * @param {number[]} nums
 * @return {boolean}
 */
// 첫 번째 코드
// var canJump = function(nums) {
//     if(nums.length === 1) return true;

//     const lastIdx = nums.length - 1;
//     const test = Array.from({length: nums.length}, () => 0);
//     test[0] = 1;

//     for(let i = 0; i < nums.length; i++){
//         if(test[i] === 0) continue;
//         const max = nums[i];
//         for(let j = 1; j <= max; j++){
//             if(i + j < nums.length) test[i + j] += 1;
//         }
//     }
    
//     return test[lastIdx] !== 0;
// };

var canJump = function(nums) {
    let goal = nums.length - 1;

    for(let i = nums.length - 2; i >= 0; i--){
        if(i + nums[i] >= goal){
            goal = i;
        }
    }

    return goal === 0;
};