55. Jump Game (점프 게임)

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.

 

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

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

 

예시 1:

입력: nums = [2, 3, 1, 1, 4]
출력: true
설명: 인덱스 0에서 1까지 1단계 점프한 다음 마지막 인덱스까지 3단계 점프합니다.

예시 2:

입력: nums = [3, 2, 1, 0, 4]
출력: false
설명: 무슨 일이 있어도 항상 인덱스 3에 도달합니다. 인덱스 3의 최대 점프 길이는 0이므로 마지막 인덱스에 도달할 수 없습니다.

 

조건:

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 10^5

정답아닌 정답:

public class Solution {
    public bool CanJump(int[] nums) {
        return Jump(nums, 0);
    }

    public bool Jump(int[] nums, int location) 
    {
        if (location == nums.Length - 1)
            return true;

        if (nums[location] != 0)
        {
            for (int i = 1; i <= nums[location]; i++)
            {
                bool isJump = Jump(nums, location + i);
                if(isJump)
                    return true;
            }
        }

        return false;
    }
}

해설: 

해당 위치에서 점프가 가능한지 재귀를 이용하여 모든 경우의 수를 탐색하여 체크해보았지만 Time Limit가 걸려 해결할 수 없었습니다.

 

정답:

public class Solution {
    public bool CanJump(int[] nums) {
        int jump = nums[0] - 1;
        
        for (int i = 1; i < nums.Length; i++)
        {
            if(jump == -1)
                return false;

            if(nums[i] > jump)
                jump = nums[i];
            jump--;
        }

        return true;
    }
}

해설: 

하지만 복잡하게 생각할 필요는 없었고 점프 횟수만큼 이동을 하다가 남은 횟수보다 더 많은 점프 횟수를 가진 곳에서 jump 횟수를 바꿔서 늘려주며 반복해주면 해결되었습니다.