[js] Leetcode 45. Jump Game II

문제

Jump Game II - LeetCode

각 배열에는 몇 칸 움직일 수 있는 지가 기록되어있다.

마지막 배열에 도달하는 최소 움직임(걸음) 수를 구하시오

 

아이디어

1. 이동거리 배열을 만들고, 직전 값을 기준으로 DP 처리하자!

2. 이전값을 기반으로 하니, 마지막 값을 도달하면 

 

구현(풀이)

var jump = function(nums) {
    const dp = nums.map(() => 99999998)
    dp[0] = 0
    for (i=0; i<nums.length; i++) {
        const maxRange = i + nums[i]+1 > nums.length ? nums.length : i+nums[i]+1
        for (j=i+1; j<maxRange; j++){
            if (dp[i] +1 < dp[j]) {
                dp[j] = dp[i] + 1
                if (j=== nums.length-1){
                    return dp[nums.length - 1]
                }
            }
        }
    }
    return dp[nums.length - 1]
};

- 구현해보니 최소 O(n) 에서 최대 O(n^2)이 나오는 거 같다.

 

남의 풀이

var jump = function(N) {
    let len = N.length - 1, curr = -1, next = 0, ans = 0
    for (let i = 0; next < len; i++) {
        if (i > curr) ans++, curr = next
        next = Math.max(next, N[i] + i)
    }
    return ans
};

내 코드의 상위호환이다.

1. curr = 현재 갈 수 있는 위치, next = 현재 위치에서 최대로 갈 수 있는 위치, N[i] + i = i번째 위치에서 최대로 갈 수 있는 위치, ans = 현재 이동한 걸음 수
2. 이를 기반으로 curr보다 큰 곳으로 이동하면 걸음 수를 증가시킨다. 

3. next가 len보다 크다는 것은 이미 현재 위치에서 마지막위치를 갈 수 있다는 의미로 반복문을 종료시키고 현재 걸음 수를 반환한다.

참고문서

리트코드 풀이 : https://leetcode.com/problems/jump-game-ii/description/