[NeetCode-LeetCode] Jump Game JAVA

반응형

728x90

[NeetCode-LeetCode] Jump Game - Medium

---

접근

• dfs
• greedy

---

풀이

배열이 주어지고 각 인덱스에는 점프할 수 있는 최댓값이 들어있다. 첫 인덱스에서 시작해 마지막 인덱스에 도달할 수 있는지 검사하는 문제이다. 인덱스의 값이 3이라면 1,2,3 세 가지 경우로 점프를 할 수 있다. 가장 간단하게 생각하면 dfs를 사용해 모든 경우를 수행해 도달이 가능한지 보면 된다. 이 문제는 그리디를 사용해 해결하는 문제로 dfs로 모든 경우를 탐색했을 때와 그리디를 사용했을 때의 성능 차이를 보려고 한다.

    public boolean canJump(int[] nums) {
        boolean[] visited = new boolean[nums.length];
    
        return dfs(nums, 0, visited);
    }

우선 dfs이다. 점프해서 갈 수 있는 모든 경우를 탐색해 보자.

    private boolean dfs(int[] nums, int index, boolean[] visited) {
        if (index >= nums.length - 1) {
            return true;
        }
        
        if (visited[index]) {
            return false;
        }
        
        visited[index] = true;
        
        int maxJump = nums[index];
        
        for (int i = 1; i <= maxJump; i++) {
            if (dfs(nums, index + i, visited)) {
                return true;
            }
        }
        
        return false;
    }

마지막 인덱스에 도달했다면 true를 반환하고 이미 방문했던 곳이라면 false를 반환한다. 그 과정을 해당 인덱스에서 점프할 수 있는 모든 범위를 다 해보며 수행하게 된다. dfs 문제라고 생각하면 정말 간단한 코드이다.

dfs

380ms라는 엄청난 숫자가 나왔다. 

---

Greedy

그리디 알고리즘은 각 상황에서 최선의 방법을 선택해 수행하는 알고리즘이다. 최선의 방법만 선택하다 보니 불필요한 선택을 패스하여 모든 선택을 했던 dfs와 얼마나 차이가 나는지 볼 수 있을 것이다. 

    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]);

            if (max >= nums.length - 1) {
                return true;
            }
        }

        return false;
    }

그리디의 코드도 간단한 편이다. max 변수를 사용해 최대 인덱스를 기록해 둔다. 배열을 순회하며 각 인덱스에서의 최대 거리로 점프하여 갈 수 있는 최대 거리를 max 변수에 기록해 둔다. 배열을 순회하며 최대 점프 거리를 계속 기록하기 때문에 각 자리에서 점프할 수 있는 모든 최대 거리에 대해 검사할 수 있게 된다. 일반적인 생각으로는 0번 인덱스에서 2번 인덱스로 점프를 했다면 2번 인덱스에서 다시 최대 거리로 점프를 하며 진행하기 때문에 만약 아래와 같이 0번 인덱스에서 1번 인덱스로 점프하면 더 멀리 갈 수 있는데 항상 최대 거리로 점프하면 저런 케이스를 놓칠 수 있는 게 아닌가? 하고 생각할 수 있다. 

nums = [2, 3, 1, 0, 3]

//항상 최대 거리로 점프하는 경우
nums[0] 최대 거리 2 점프 -> nums[2]
nums[2] 최대 거리 1 점프 -> nums[3]
nums[3] 최대 거리 0

//최선의 선택을 하는 경우
nums[0] 1 점프 -> nums[1]
nums[1] 3 점프 -> nums[4] -> 마지막 인덱스 도달

저렇게 nums [0] -> nums [2] -> nums [3] 형태로 탐색을 하는 것이 아닌 nums [0] -> nums [1] -> nums [2] 순차적인 형태로 모든 인덱스에서 다 탐색을 하기 때문에 모든 경우를 놓치지 않고 탐색할 수 있다. 그렇게 탐색의 종료 조건으로 i가 max보다 클 경우 탐색이 false로 종료되는데 i가 max 보다 크다는 경우는 0번 인덱스에 시작해 해당 i번 인덱스에 어떤 방법을 써도 도달할 수 없기 때문에 마지막 인덱스까지 도달할 방법이 없다는 것을 뜻한다. 기본적으로 max 번째 인덱스에 있는 값만큼 점프를 해 다음 인덱스로 도달할 수 있는데 이미 max 번째 인덱스에서 최대 거리로 점프한 값이 i 보다 작다는 뜻으로 더 이상 진행이 불가능하다는 소리다. 문제없이 배열의 길이를 넘어가게 되면 true를 반환하게 된다. 

greedy

380ms와 2ms는 유의미한 차이를 보여주는 수치이다. 

---

전체 코드

dfs

class Solution {
    public boolean canJump(int[] nums) {
        boolean[] visited = new boolean[nums.length];
    
        return dfs(nums, 0, visited);
    }   

    private boolean dfs(int[] nums, int index, boolean[] visited) {
        if (index >= nums.length - 1) {
            return true;
        }
        
        if (visited[index]) {
            return false;
        }
        
        visited[index] = true;
        
        int maxJump = nums[index];
        
        for (int i = 1; i <= maxJump; i++) {
            if (dfs(nums, index + i, visited)) {
                return true;
            }
        }
        
        return false;
    }
}

 

greedy

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]);

            if (max >= nums.length - 1) {
                return true;
            }
        }

        return false;
    }   
}