[Leetcode] 55. Jump Game - JS

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

 

1. 문제 분석

문제분석
--------------------
- 정수 배열 nums
- 처음에 배열 첫번째 인덱스에 위치함
- 각 배열의 요소는 현재 위치에서 최대 점프 가능한 길이
- 마지막 인덱스에 도달할 수 있으면 true, 그렇지 못하면 false를 반환

제한조건
--------------------
- 1 <= nums.length <= 10^4
- 0 <= nums[i] <= 10^5

 

2. 접근 방법

현재 위치 + 현재 위치의 최대 점프 >= 목표 위치를 만족하는지 안하는지를 확인한다.

- goal = 목표 위치 인덱스
- 역순으로 goal 직전에서부터 첫번째 인덱스로 순회한다.
만약 위에서 언급한 조건에 성립하면, goal 을 현재 위치로 이동한다.

왜냐하면, 현재 위치에서 목표 위치는 도달할 수 있으므로 
다음에 확인해야할 것은 현재 위치를 목표위치로 했을 때, 
이전 인덱스에서 도달할 수 있는지 확인해야하기 때문이다.

반복문 순회가 종료되었을 때, 목표 위치가 처음 인덱스 위치에 도달하면 처음 인덱스 위치도 목표에 도달할 수 있다는 의미이다.


ex)

[2,3,1,1,4]
       i g
--------------------
현재 인덱스(3) + 최대 점프(1) >= 목표 인덱스(4) 만족하므로,
목표 인덱스에 현재 인덱스를 할당한다.


[2,3,1,1,4]
     i g
--------------------
현재 인덱스(2) + 최대 점프(1) >= 목표 인덱스(3) 만족하므로,
목표 인덱스에 현재 인덱스를 할당한다.


[2,3,1,1,4]
   i g
--------------------
현재 인덱스(1) + 최대 점프(3) >= 목표 인덱스(2) 만족하므로,
목표 인덱스에 현재 인덱스를 할당한다.


[2,3,1,1,4]
 i g
--------------------
현재 인덱스(0) + 최대 점프(2) >= 목표 인덱스(1) 만족하므로,
목표 인덱스에 현재 인덱스를 할당한다.

 

 

3. 코드

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;
};

 

- 반복문 순회 문제가 잘 안풀릴 때는 역순으로 접근해보는 방법을 고려해보자.

 

4. 복잡도 분석

- 시간복잡도: O(n)

- 공간복잡도: O(1)