[LeetCode] 55. Jump Game - 아이디어(Idea) + 깊이우선탐색(DFS) + 동적계획법(DP, Dynamic Programming) JAVA

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

코드설명

깊이우선탐색(DFS) + 동적계획법(DP, Dynamic Programming) 를 활용합니다.

 

최악의 경우 O( (10^4)^(10^4) ) 의 시간복잡도입니다.

nums의 길이가 10^4 이기에 최악의 경우 모든 칸을 다 방문할경우 그렇습니다.

동적계획법을 사용할 경우 O (10^4) ) 입니다. 즉, nums.length의 최대값입니다. (배열의 길이만큼)

코드 

정답코드1입니다. goal의 전 위치에서부터 시작해, 전 위치에서 이동하여 해당 goal 지점에 도달할 수 있다면, goal을 처리할 수 있다는 의미이므로, goal의 위치를 바꾸어줍니다.

뒤에서부터 처리한다는점, 그리고 i + nums[i], 즉 해당 범위안에 존재한다면 바로 위치를 바꾸어버린다는점이 매우 인상 깊었습니다.

class Solution {
    public boolean canJump(int[] nums) {
        int goal = nums.length - 1;
        for(int i=nums.length - 2 ; i>=0; i--){
            //it means goal can be acheived from i.
            if(i + nums[i] >= goal){
                goal = i;
            }
        }
        return goal == 0 ? true : false;
    }
}

 

정답코드1입니다.

class Solution {
    int[] cache = new int[10000 + 1];
    public boolean canJump(int[] nums) {
        //Time Compleixity 가 (10^4)^10^4 =
        // [10^5, 10^5, 10^5, 10^5, 10^5... ]이게 10^4까지 있으면
        Arrays.fill(cache, -1);
        return jump(nums, 0) < 1 ? false : true;
    }

    int jump(int[] nums, int pos){
        if(pos == nums.length - 1){
            return cache[pos] = 1;
        }
        if(nums[pos] == 0) return cache[pos] = -2;
        if(cache[pos] != -1) return cache[pos];
        int ret = -2;
        for(int i=1; i<=nums[pos] && pos + i < nums.length; i++){
            ret = Math.max(ret, jump(nums, pos + i));
        }
        return cache[pos] = ret;
    }
}