LeetCode - Jump Game 2

문제 설명

자연수 배열이 주어진다. 배열의 첫 인덱스 부터 시작해서 마지막 index까지 Jump를 해서 도착해야 한다.

각각의 배열의 원소가 가리키는 값은 그 자리에서 jump 할 수 있는 거리를 가리키며,

마지막 Index까지 도착했을때 최소의 jump 횟수를 찾아라 라는 것이 문제다.

해결방법

제일 먼저 떠오른 방법은 동적계획법이다.

참,, 난 Greedy 문제를 풀러왔는디,,

아무튼 어떻게 하면 풀 수 있을까 머리를 굴려보다가

jumps 배열을 생성하고

jumps[0] = 0 으로 설정하고 이중 포문을 설정해서 $Math.min(jumps[j],jump[i]+1)$ 을 해두면

모든 배열에 대한 각각의 최소 jump 거리값을 구할 수 있다.

Code

import java.lang.*;
import java.util.*;
class Solution {
    public int jump(int[] nums) {
        int[] jumps = new int[nums.length];
        Arrays.fill(jumps,Integer.MAX_VALUE);
        jumps[0] = 0;
        for(int i=0; i<jumps.length; i++){
            for(int j=i+1; j<=i+nums[i]&&j<nums.length; j++){
                jumps[j] = Math.min(jumps[i]+1,jumps[j]);
            }
        }
        return jumps[nums.length-1];
    }
}

소감

아무래도 모든 경로의 수를 구하다 보니 $O(n^2)$ 이 되버린다.

아마 $O(n)$ 방식의 시간복잡도가 있는 모양이다.

찾아보니 2 Pointer를 이용해서 해결하는 방법이 있더라.

시간복잡도는 좀 줄여야 겠지만

예전에 비해 문제 푸는 속도가 매우 줄었다. 라고 합리화를 해본다...