[C++] LeetCode : Jump Game

Question

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

 

정수 배열 숫자가 제공됩니다. 처음에는 배열의 첫 번째 인덱스에 위치하며 배열의 각 요소는 해당 위치에서 최대 점프 길이를 나타냅니다.

마지막 인덱스에 도달할 수 있으면 true를 반환하고 그렇지 않으면 false를 반환합니다.

 

제약사항

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 105

---

Solution

가능한 최선의 수행 시간(Best Conceivable Runtime(BCR)

• 배열의 원소를 한번씩은 봐야 하기 때문에 O(n) 

고려사항

• 모든 원소를 다 볼 필요가 있는가? 

---

Solution1 - Dynamic Programming

현재 인덱스의 값을 기준으로 다음 가능한 인덱스까지 가능한지 체크를 한다. 사실 마지막 인덱스에 도착 가능한 경우 나머지 원소를 볼 필요가 없기 때문에 return 해준다.

class Solution {
public:
    bool canJump(vector<int>& nums) {
        bool possible[100001] = {0};
        
        possible[0] = true;
        
        for(int i=0; i<nums.size(); i++){
            if(possible[i]){
                for(int j=0; j<=nums[i]; j++){
                    if(i+j >= nums.size()) return true;
                    possible[i+j] = true;
                }
            }
        }
        
        return possible[nums.size()-1];
    }
};

• Time complexity : O(n²) 
• Space Complexity : O(n) 

Solution2 

사실 첫번째 index를 기준으로 잡고 계속 나아간다고 가정한다. 나아가면서 현재 가능한 값을 계속 초기화 및 -- 연산을 통해 가능 여부만 체크하면 O(n)에 해결할 수 있다.

 

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int curr = nums[0];
        
        for(int i=1; i<nums.size(); i++){
            if(curr <= 0) return false;
            curr--;
            curr = max(curr, nums[i]);
        }
        
        return true;
    }
};

• Time complexity : O(n) 
• Space Complexity : O(1) 

출처 : https://leetcode.com/explore/interview/card/top-interview-questions-medium/111/dynamic-programming/807/

Explore - LeetCode