[Leetcode] 55. Jump Game

Identifying the Problem

최대 nums의 값만큼 다음 index로 넘어가 끝까지 도달하면 true 도달하지 못하면 false 를 리턴한다.

 

Ex : Input: nums = [2,3,1,1,4] Output: true

Explanation: nums[0]에서 1칸 or 2칸 점프가능하고, 2칸 점프했을 때, nums[2] 에서 1칸 점프, nums[3]에서 1칸 점프                      nums[4] 도달하므로 true

 

Input: nums = [3,2,1,0,4] Output: false

Explanation: nums[3] 에서 0이고 더 이상 진행이 불가능하다.

Organizing thoughts

size가 1일 때에는 무조건 true 가 되도록 하고, 그 이후를 어떻게 하면 좋을지 생각해보자

예시에서 보았듯 nums[i] 가 무슨 값인지에 따라, nums가 진행가능한 범위가 정해진다.

즉 진행가능한 범위에 nums의 마지막 index가 들어오면 true를 리턴하고, 불가능하면 false 리턴하면 된다.

 

 

 

Sourcecode

dp 를 사용해 직접 작성한 코드이다.

하지만 시간복잡도가 O(n²) 이므로 Time Limit Exceeded가 떴다.

class Solution {
public:
    bool canJump(vector<int>& nums) 
    {
        vector<int> dp(nums.size(),0);
        
        dp[0] = 1; //초기값 true
        
        for(int i=0; i<nums.size()-1 ; i++) //마지막 이전까지 진행
        {    
            if(dp[i] > 0) //index가 범위 안에 있다면
            {   
                for(int k=0; k<nums[i]; k++) //해당 index가 더 나아갈 수 있는 범위를
                    if(i+1+k < nums.size())  //size를 벗어나지 않는 선에서 추가한다.
                        dp[i+1+k] = 1;
            }
        
        }
            
        return dp[nums.size() - 1]; //마지막이 범위에 들어오는지 아닌지에 따라 true / false
    }
};

 

아래는 가장 간단하고 직관적인 코드이다.

출처 

Linear and simple solution in C++ - LeetCode Discuss

 

bool canJump(vector<int>& nums) {
    int size=nums.size();
    int step=nums[0];
    //nums의 값만큼 앞으로 갈 수있게 step 설정
    
    for(int i=1;i<size;++i){ 
        step--; //다음 index로 넘어갈 때마다 step 감소
        if(step<0) //step 이 0보다 작아지면, 더 나아갈 수 없으므로 false
           return false;
           
        if(nums[i]>step) // nums[i] 값이 step보다 크다면 더 많이 나아갈 수 있으므로 step 교체
           step=nums[i];
    }
    
    return true; //defalut 값 true
}