[LeetCode] Jump Game - Javascript

Jump Game

[요소의 수만큼 점프하기]

제약 조건 

1 <= prices.length <= 3 * 10^4
0 <= prices[i] <= 10^4

Example

ex1) Input: nums = [2,3,1,1,4]
     Output: true
     Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

ex2) Input: nums = [3,2,1,0,4]
     Output: false
     Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

초기 접근 방식

항상 맨 처음 주어진 테스트 케이스 2~3개만 통과하자는 마음으로 문제를 풀기에,

맨 마지막 배열을 기준으로 배열 인덱스의 값 중 "0"이 있는지 확인하고 0이 존재하지 않으면 true를 반환하고

"0"이 존재하면 0인덱스의 위치와 배열의 마지막 인덱스의 거리를 비교해 그 수와 큰지 비교하는 방식으로 접근을 했다.

초기 전체코드

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function (nums) {
   let target = nums.length - 1;
   let cnt = 0;

   for (let i = target - 1; i >= 0; i--) {
      if (nums[i] === 0) {
         cnt++;
      } else {
         if (nums[i] > cnt) {
            return true;
         } else {
            return false;
         }
      }
      return false;
   }
   return true;
};

 

해당 코드로 주어진 아래의 testcase 2개를 통과하여 제출을 했다.

ex1) Input: nums = [2,3,1,1,4]
     Output: true
     Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

ex2) Input: nums = [3,2,1,0,4]
     Output: false
     Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

다시 생각 해보며..

하지만 전체의 172개의 testcase 중 130개만 통과를 하여, 코드에 문제가 있음을 느꼈다.

먼저 실패한 testcase는 아래와 같다.

ex3) Input: nums = [0,2,3]
     Output: false

그렇다,, 이 방식대로 풀이를 하면 배열 인덱스 0번째에 값이 0이거나 인덱스의 값들이 0,1,0,1,4와 같이 되어있으면

점프를 해보지도 못하고 false를 반환한다.

 

solve 전체 코드

var canJump = function (nums) {
   let max = 0;
   for (let i = 0; i < nums.length; i++) {
      if (i > max) {
         return false;
      }
      max = Math.max(nums[i] + i, max);
   }

   return true;
};

생각을 다르게 해서 배열의 첫 번째 인덱스부터 시작해 현재 반복문 지점 i와 max 값을 비교해 

현재 인덱스 번호가 더 크다면 flase를 반환한다. 

만약 i가 max보다 크다면 도달하지 못하는 곳이 되기 때문이다.

아니라면 현재 인덱스의 값과 i를 더해 max 값을 선별한다. 즉 max 값은 최대 어느 인덱스까지 점프를 할 수 있는지 계속 저장하는 것이다.

반복문을 모두 수행했음에도 i가 max보다 더 큰 경우가 없다면 true가 되기에 그때 리턴을 한다.