[LeetCode] 55. Jump Game - Java[자바]

링크

문제

정수 배열의 개수가 주어집니다. 처음에는 배열의 첫 번째 인덱스에 위치하게 되며, 배열의 각 요소는 해당 위치에서 최대 점프 길이를 나타냅니다.

마지막 인덱스에 도달할 수 있으면 참을 반환하고, 그렇지 않으면 거짓을 반환합니다.

풀이

완탐이 가능하려나 생각을 먼저 한 것 같다. 터무니 없이 경우의 수가 많다.

역으로 가자.., 그리디한 느낌으로 마지막 인덱스 지점에서부터 시작해서 도달할 수 있는지를 체크한다..?

결국 DP나 그리디 쪽으로 풀어야되겠다는 생각이 들었다.

그리디 코드

class Solution {  
    public boolean canJump(int[] nums) {  
        int lastIndex = nums.length - 1;  
        for (int curIndex = nums.length - 1; curIndex >= 0; curIndex--) {  
            if (curIndex + nums[curIndex] >= lastIndex) {  
                lastIndex = curIndex;  
            }  
        }  
        return lastIndex == 0;  
    }  
}

마지막 위치에서 부터 0까지 current Index에서 점프할 수 있는 최대 거리가 lastIndex 보다 크면, lastIndex를 갈아끼워준다.

그냥 점프 여부로만 판단할 수 있으므로 dp보다 훨씬 편하게 풀 수 있을거라 생각했다.

dp는 그냥 귀찮아서 생략..

public class Solution {  
    public boolean canJump(int[] nums) {  
        int n = nums.length;  
        int[] dp = new int[n];  
        
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[n - 1] = 0;  
  
        for (int i = n - 2; i >= 0; i--) {  
            dp[i] = Math.min(nums[i], n - 1 - i);  
            for (int j = i + 1; j <= i + dp[i] && j < n; j++) {  
                if (dp[j] < Integer.MAX_VALUE) {  
                    dp[i] = Math.min(dp[i], 1 + dp[j]);  
                }  
            }  
            if (dp[i] == Integer.MAX_VALUE) {  
                return false;  
            }  
        }  
        return dp[0] < Integer.MAX_VALUE;  
    }  
}

하려다가 설명을 적자면, 일단 배열의 길이만큼 dp 배열을 생성하고

각 index에서 점프 수를 계산한다.. 그냥 접어두고 그리디로 풀자..