[LeetCode] - M - Jump Game

https://leetcode.com/problems/jump-game/?envType=study-plan-v2&envId=top-interview-150

Jump Game - LeetCode

 

📌 - 의사 코드 및 풀이

1. boolean 배열 추가, bool[0] = true 초기화
2. 0부터 끝까지 반복문을 진행
3. if(bool[i]가 참일때) i의 위치부터 i의 값만큼 bool 배열 true
4. 마지막 인덱스의 bool값을 출력

 

이중 포문을 사용해서 역시나 시간 복잡도에 대한 측면이 최악으로 나왔다.

 

이걸 개선하기 위해서 이중포문을 없애야 하고 그 방식은 아래에서 다시 풀이하도록 한다.

🔥 - Java 코드

class Solution {
    public boolean canJump(int[] nums) {
        boolean[] check = new boolean[nums.length];
        check[0] = true;

        for(int i =0;i<nums.length;i++){
            if(check[i]){
                for(int j = i; j<=i+nums[i];j++){
                    if(j>=nums.length){
                        break;
                    }
                    check[j] = true;
                }
            }
        }

        return check[nums.length-1];
 
        
    }
}

 

---

 

 

📌-  개선된 풀이

다른 신기하고 간단한 풀이가 있어서 가져와봄

-> distance를 지정하고 for문을 돌면서 distance의 최댓값 안에 마지막 인덱스가 포함되면 true를 반환하고, 그게 아니라면 false 반환

 

🔥 - Java 코드

class Solution {
    public boolean canJump(int[] nums) {
        int distance =0;
        for(int i =0; i<=distance;i++){
            distance = Math.max(distance,i+nums[i]);
            if(distance >= nums.length-1){
                return true;
            }
        }
        return false;
        
    }
}