Jump Game

점프 게임

Jump Game - LeetCode

 

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

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

 

예 1:

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

예 2:

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

제약:

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

 

---

1.첫번째 시도

    public boolean canJump(int[] nums) {
        

        int length = (nums.length)-1;
        boolean result = true;
        for(int i = 0 ; i<length ; i++){
            
            if(nums[i]>=length){
                result = true;
                break;
            }

            if(nums[i]==0){
                result = false;
                break;
            }

        }
          return result;
    }

배열에 인덱스 i번째가 0이 아니면 어떻게서든 마지막 인덱스에 도착 할 수 있을 거라고 판단하였고,

i번째의 수가 배열의 length-1보다 크거나 같다면 마지막 인덱스에 도착 할 수 있을거라고 판단하였다.

하지만

[1,2,0,1] 의 배열에서의 테스트에 통과하지 못했습니다.

 

2.두번째 시도

    public boolean canJump(int[] nums) {
        

        int length = (nums.length)-1;
        boolean result = false;
        
        for(int i = 0 ; i<length ; i++){
            if(length-i<=nums[i]){
                result= true;
                break;
            }
        }
          return result;
    }

두번째 방법은 i번째 수가 length-i 보다 크거나 같으면 마지막 i번째에 도달할 것이라고 생각하였다

하지만 

[0]의 배열에서의 테스트에 통과하지 못했습니다.

 

3.세번째 시도

    public boolean canJump(int[] nums) {
        

        int length = nums.length; //5
        boolean result = false;
        if(length<=1){
            return true;
        } 

        for(int i = 0 ; i<length-1; i++){

            if((length-1) - i <=nums[i]){
                result= true;
                break;
            }
        }
          return result;
    }

 

두번째 시도에서 발생했던 조건을 처리하기 위해 length가 1이하면 무조건 도달 할 것이라고 생각하여 조건을 추가하였습니다.

하지만

[0,2,3]의 배열에서의 테스트에 통과하지 못했습니다.

 

4.세번째 시도 (성공 )

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

사고를 전환해서 최대 갈 수 있는 수를 찾기로 했다 .

i+jump와 maxJump중 큰 수가 maxJump가 되고  maxJump가 nums.length - 1와 크거나 같다면 마지막에 도달 할 수있다고 생각하였다.

그리고 maxJump의 초기값을 0으로 설정하여 첫 인덱스의 값이 0이면 스타트도 할 수 없기 때문에 적절한 조건문이라고 생각하였다.