LeetCode 55 - Jump Game

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

 

• 입력
  • int [] nums
• 출력
  • 마지막 인덱스에 도달할 수 있는지 여부 boolean

메모이제이션

첫 위치는 0번 인덱스에서 시작된다. 그리고 해당 인덱스의 값인 nums [i]는 최대 점프 길이를 뜻한다.

먼저 문제를 이해하기 이해 하나씩 해보겠다.

[2, 3, 1, 1, 4] 의경우 idx 기준으로 0 → 1→ 4 가 가능하다. 또 0 → 2→ 3 → 4로도 가능하다.

다른 경우를 하나 더 생각해보자. 0 → 1 → 2 → 3 → 4의 경로도 가능하다.

위의 예시에서 보면 알 수 있는 게 있다. 바로 2 → 3 → 4가 반복되고 있다는 것이다.

다시 말해 해당 번호에서 출발하는 경로가 반복돼서 나타나는데 만약 그 경로로부터 도착할 수 없다면 더 이상 탐색할 필요가 없다는 것이다.

필요한 것은 해당 idx에서 도달 가능한 지를 저장하는 테이블이다.

class Solution {
    public boolean canJump(int[] nums) {
	  // false와 true만 있으면 판정이 힘들기 때문에 null이 가능하도록 Boolean 배열로 생성
        Boolean[] isPossible = new Boolean[nums.length];
        return dfs(0, nums, isPossible);
    }

    private boolean dfs(int v, int[] nums, Boolean[] isPossible) {
        if (v >= nums.length - 1) {
            return true;
        }

        if (isPossible[v] != null) {
            return isPossible[v];
        }

        for (int u = v + 1; u <= v + nums[v]; u++) {
            if (dfs(u, nums, isPossible)) {
	            // 재귀를 모두 통과했다는 것은 방문이 가능하다는 것.
                return isPossible[v] = true;
            }
            if (u >= nums.length - 1) {
            // 범위를 벗어난 것은 볼 필요 없다.
                break;
            }
        }
				// 모든 지점을 확인했는데도 true를 리턴하지 못했다는 것은 방문하지 못한다는 것
        return isPossible[v] = false; 
    }
}

하지만 이 알고리즘은 최악의 경우 O(N^2)의 시간복잡도를 가진다. 실제로는 메모이제이션으로 인해 더 적은 시간이 소요되겠지만 여전히 비효율적이다.

그리디 알고리즘

각 위치에서 최대한 멀리 갈 수 있는지를 판단하면 전체적인 도달 가능성을 확인할 수 있다.

즉 현재 최대로 도달 할 수 있는 위치를 기록하고 현재 인덱스가 그보다 크면 도달할 수 없다는 뜻이므로 false를 반환한다.

도달할 수 있다면 최대 도달 위치를 갱신해 준다.

class Solution {
    public boolean canJump(int[] nums) {
        int max = 0; // 도달할 수 있는 최대 위치

        for (int i = 0; i < nums.length; i++) {
            // 최대 이동 위치보다 먼 곳 = 도달할 수 없는 곳
            if (i > max) {
                return false;
            }
            // 만약 현재 위치에서 더 멀리 갈 수 있다면 그 위치로 최대 위치를 갱신
            max = Math.max(max, i + nums[i]);
        }

        return true;
    }
}

이 방법이면 O(N)의 시간복잡도로 해결이 가능하다.