[leetcode - 45. Jump Game II] java

문제 설명

1. 배열이 주어진다.

2. 최대 거기 적힌 숫자만큼 점프할 수 있다.

3. 목적지에 도달할 수 있는 최소 점프 갯수를 구하면 된다.

풀이 과정 

- DP 문제인데, 그냥 이중 for문으로 푸니까 쉬웠는데 문제에서 원했던 것은 하나의 for문으로 푸는 것 같았다.

- 그래서 문제를 살펴보니(DP라는건 최소를 구하는 배열이니 미리 알고있었어서 이를 통해서 구하는걸로 마음먹음) 한번에 갈 수 있는 위치 중 가장 먼 위치가 목적지가 된다면, 그게 정답이라는 것이었다.

풀이 과정은 다음과 같다.

1. 먼저 현재 위치에서 점프할 수 있는 최대 거리를 구한다.

2. 그리고 과거에 점프해서 도달했던 최대 거리가 지금 위치라면

3. (1)에서 구한 최대 거리가 다음번의 최대 거리가 될 것이고

4. 목적지에 도달하기 위해서는 점프가 한번 더 필요하다는 것이다.

5. 근데 (4)에서 점프를 뛰었다고 치고, (2)의 최대 거리가 목적지라면 그냥 그게 정답이 된다.

코드

class Solution {
    public int jump(int[] nums) {
        if (nums.length <= 1) return 0;
        
        int ans = 0;
        int currentMax = 0; // 현 위치에서 도달한 최대 거리
        int nextMax = 0; // 다음 점프로 도달할 수 있는 최대 거리
        
        for (int i=0; i<nums.length - 1; i++) {
            nextMax = Math.max(nextMax, i + nums[i]); // 다음번에 점프로 갈 수 있는 최대 위치
            
            if (i == currentMax) { // 과거에 올 수 있던 가장 먼 위치가 여기라면
                ans++; // 이 점프는 뛰어야 했던거임
                currentMax = nextMax; // 그리고 이번에 가장 멀리 갔던 위치를 저장한다.
                
                if (currentMax >= nums.length - 1) { // 가장 멀리 갔던 위치가 목적지라면 더 안뛰어도 된다.
                    break;
                }
            }
        }
        
        return ans;
    }
}