[LeetCode] 55. Jump Game (javascript)

주어진 배열이 있다.

인덱스 0에서 시작하는데, 

요소의 숫자만큼 점프를 할 수 있다.(더 짧게 뛰어도 된다.)

이때, 배열의 끝까지 갈 수 있는지 검사하는 문제이다.

 

 

Input: nums = [2,3,1,1,4] Output: true 

nums[0]=2에서 두칸, nums[2]=1에서 한칸, nums[3]=1에서 한칸 가면 도착한다.

nums[0]=2에서 한칸, nums[1]=3에서 세칸 가면 도착한다.

 

 

Input: nums = [3,2,1,0,4] Output: false

nums[0]=3에서 세칸을 가도, nums[1]=2에서 두칸을 가도, nums[2]=1에서 한칸을 가도 마지막 요소에 도달할 수 없다.

그러므로 false이다.

 

 

이 문제를 접했을 때... DFS로 풀어야 하나? 아니면 브루트포스?? 하고 약간 삽질을 했는데

문제의 카테고리가 그리디인것을 보고 아 최적인 접근법이 있겠구나 생각했다.

 

1. 0이 하나도 없으면, 무조건 끝까지 갈 수 있다.

[1,1,1,1,1] 모든 요소가 1 이상이라면 계속 지나갈 수 있기 때문이다.

 

2. 0이 있는 경우는 두 가지로 나뉜다.

  - 앞 요소 중 이 0을 건너뛸 수 있을만큼 긴 점프가 있다면 지나갈 수 있다.

예를들어

[1, 2, 0, 1]라면, nums[2]=0을 지나기 위해선 바로 앞 요소 nums[1]이 2 이상이어야 한다.

(그래야 nums[3]으로 갈 수 있으므로.)

또는 앞앞 요소 nums[0]이 3 이상이어야 한다.

...

그러므로 nums[i]==0일때 지나가기 위해선, 

nums[i-j-1] > j+1 이어야 한다.

 

  - 마지막 요소가 0인 경우, 건너뛰지 않고 해당 요소까지만 도착할 수 있으면 된다.

예를들어

[..., 2, 1, 0]인 경우 0의 앞 요소가 2 이상이 아니라 1 이상만 되어도 마지막에 도착한다.

앞앞 요소는 2 이상만 되면 된다.

...

그러므로 nums[nums.lengh-1] == 0일땐 nums[i-j-1]>j 이면 된다.

 

추가로 

- 배열의 길이가 1이면 항상 가능하다.

    [0], [1]  출발하자마자 도착이므로...

- 첫 요소가 0이라면 불가능하다.

    [0, 100] 나아갈 수 없으므로..

 

 

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
    if(nums.length == 1) return true;
    // 첫 요소가 0이라면 불가능하다.
    if(nums[0] == 0) return false;
    
    // 0이 하나도 없으면, 무조건 끝까지 갈 수 있다.
    if(nums.indexOf(0) < 0) return true;
    
    // nums[i] == 0인 경우, 앞의 요소들이 nums[i-1] > 1, nums[i-2] >2 , nums[i-3] > 3 ... 인게 하나라도 있으면 지나갈 수 있다.
    for(let i = 1; i<nums.length;i++){
        // 0을 발견한 경우에만 확인한다.
        if(nums[i] == 0) {
            console.log(i,'번째에서 0 찾음');
            let flag = false;
            // 찾은 0의 인덱스 i부터 앞으로 검사해 나간다. [i-j-1]
            for(let j = 0; j<i;j++){
                console.log('j',j,'nums[i-j-1]', nums[i-j-1]);
                // 찾은 0이 마지막 요소인 경우에는, 넘어 지나갈 필요가 없으므로 j+1이 아니라 j보다만 크면 된다.
                // ex. [1, 0]
                if(i == nums.length-1 && nums[i-j-1]>j){
                    console.log(nums[i-j-1],'이', j, '보다 크고, 마지막 요소이므로 성공함');
                    flag = true;
                    break;
                }
                // 찾은 0이 마지막 요소가 아닌 경우에는, j+1보다 커야 지나갈 수 있다.
                // ex. [1, 0, 1] // 지나갈 수 없음
                // ex. [2, 0, 1] // 지나갈 수 있음
                else if(nums[i-j-1]>j+1) {
                    console.log(nums[i-j-1],'이', j+1, '보다 커서 지나갈 수 있음')
                    flag = true;
                    break;
                }
            }
            if(!flag) return false;
        }
    }
    
    return true;
};

재밌게 푼 문제지만..

시간제한이 있고 문제만 제시받은 상황에서는 이 아이디어를 떠올릴 수 있었을지 잘 모르겠다.

 

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