LeetCode 45 - Jump Game2

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

 

마지막 인덱스 위치에 도달하기까지 최소 점프 횟수를 구하는 문제이다.

예를 들어 i에 위치해 있다면 0≤j≤nums [i]인 j 만큼 점프할 수 있다.

항상 마지막 인덱스에 도달할 수 있다고 가정한다.

DFS, 브루트포스

예제를 따라서 해보다 보면 먼저 떠오르는 것은 DFS이다.

DFS를 통해서 모든 가능성을 탐색하고 최소 횟수를 계산하는 것이다.

class Solution {

    static final int INF = Integer.MAX_VALUE;

    public int jump(int[] nums) {
        return dfs(0, nums);
    }

    private int dfs(int pos, int[] nums) {
        System.out.println(pos);
        // 종료조건
        if (pos >= nums.length - 1) {
            // 마지막 위치이상이면 더 이상 점프 불필요
            return 0; 
        }
        // 재귀호출
        int minJumps = Integer.MAX_VALUE;
        for (int i = 1; i <= nums[pos]; i++) {
            int jumps = dfs(pos + i, nums);
            if (jumps != INF) {
                minJumps = Math.min(minJumps, jumps + 1);
            }
        }

        return min;
    } 
}

하지만 모든 경로를 확인하기 때문에 비효율적이다. 생각해보면 과정에서 반복적으로 나오는 부분들이 생긴다.

예를 들어 0 → 3 이나 1 → 3이나 결국 3에서의 점프 횟수가 해당 과정들에 더해지게 된다.

그러면 3에서의 점프 횟수를 저장해 놓으면 더 빠른 계산이 가능할 것이다.

즉 메모이제이션 기법을 사용하면 개선이 가능해진다

class Solution {

    static final int INF = Integer.MAX_VALUE;
    static int[] mem;

    public int jump(int[] nums) {
        mem = new int[nums.length + 1];
        Arrays.fill(mem, INF);

        return dfs(0, nums);
    }

    private int dfs(int pos, int[] nums) {
        // 종료조건
        if (pos >= nums.length - 1) {
            // 마지막 위치이상이면 더 이상 점프 불필요
            return 0; 
        }

        // 이미 확인한 경로면 바로 리턴
        if (mem[pos] != INF) {
            return mem[pos];
        }

        // 재귀호출
        int minJumps = Integer.MAX_VALUE;
        for (int i = 1; i <= nums[pos]; i++) {
            int jumps = dfs(pos + i, nums);
            if (jumps != INF) {
                minJumps = Math.min(minJumps, jumps + 1);
            }
        }

        return mem[pos] = minJumps;
    } 
}

개선은 됐지만 여전히 비효율적이다. 제출 결과를 보니 129ms로 아주 느린 결과를 보였다.

 

그리디 알고리즘

다시 예제를 분석해보자.

[2, 3, 1, 1, 4]에서 최소 점프 횟수는 2이다. 0 → 1 → 4 인덱스로 점프하는 경로다.

각 위치에서 가장 멀리 갈 수 있는 곳으로 점프하는 것이 유리해 보였으나 이 예제를 보면 항상 최대 거리로 점프하는 것이 최적의 해답이 되는 것은 아니라는 것을 확인할 수 있다.

현재 위치에서 도달할 수 있는 최대 범위와 그 범위 내에서 다음 점프로 갈 수 있는 최대 범위를 관리하면 문제를 해결할 수 있을 것 같다.

그렇다면 관리해야 할 변수는 3가지가 된다.

• 현재 위치
• 현재 도달 가능 최대 위치
• 다음 점프 도달 최대 위치

class Solution {
    public int jump(int[] nums) {
        int jumps = 0;
        int currMax = 0;
        int nextMax = 0;

        // 마지막 위치는 확인이 불필요
        for (int i = 0; i < nums.length - 1; i++) {
            
            // 다음 점프로 도달 가능한 최대 위치
            nextMax = Math.max(nextMax, i + nums[i]);

            // 현재 도달 가능한 최대 위치 도달
            if (i == currMax) {
                jumps++;
                currMax = nextMax;

                // 이미 마지막 인덱스면 종료
                if (currMax >= nums.length - 1) break;
            }
        }

        return jumps;
    }
}

이 풀이는 1ms의 결과를 보이며 아주 빠른 속도로 문제 풀이가 가능헀다.