[LeetCode] 55. Jump Game - Java

 

Jump Game - LeetCode

 

문제

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.

 

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

 

Constraints:

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

 

정수 배열 nums가 주어지고, 처음에는 배열의 첫 번째 인덱스에 위치한다.

배열의 각 요소는 해당 위치에서 최대로 점프할 수 있는 길이를 나타낸다.

마지막 인덱스에 도달할 수 있는 경우 true를 반환하고, 도달할 수 없는 경우 false를 반환한다.

 

---

 

내 풀이

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

이 문제도 비교적 쉽게 풀었다.

일단 점프 가능한 인덱스인 indexCanJump 를 0으로 초기화 한 뒤 배열을 순회한다.

현재 인덱스인 i가 indexCanJump 보다 크면 점프가 불가능하므로 false를 반환한다.

 

• 시간복잡도 : O(n)
• 공간복잡도 : O(1)

 

최선의 시간, 공간 복잡도로 잘 푼 것 같다.