[LeetCode/Top Interview 150] [Array / String] 55. Jump Game

문제 링크: https://leetcode.com/problems/jump-game/?envType=study-plan-v2&envId=top-interview-150
사용 언어: Java(OpenJDK 17. Java 8)

난이도: medium

문제:

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

전략:

그래프 탐색문제같이 생기긴 했지만 배열이 1개이므로 이를 활용해서 효율적으로 풀 수 있지 않을까 싶다.
1개짜리 배열은 그냥 true 리턴해주기

코드 구현:

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

실행결과:
Time: 2 ms (80.25%), Space: 44.3 MB (54.48%) - LeetHub
https://github.com/1-vL/LeetCode/blob/main/0055-jump-game/0055-jump-game.java

개선 방안:

도달여부 체크하는 if 문 도약 가능 거리갱신한 경우에만 도달하도록 수정

class Solution {
    public boolean canJump(int[] nums) {
        if (nums.length==1) {
            return true;
        }
        
        int possible = nums[0];
        for (int i=0;i<nums.length-1;i++) {
            if (possible >= i) {
                possible = Math.max(nums[i]+i, possible);
                if (possible >= nums.length-1) {
                    return true;
                }
            }
        }
        return false;
    }
}
	Accepted	2 ms	44.2 MB	java

Discuss 탭의 타인 코드:

class Solution {
    public boolean canJump(int[] nums) {
       int reachable = 0;
       for(int i = 0; i < nums.length; i ++) {
           if(i > reachable) return false;
           reachable = Math.max(reachable, i + nums[i]);
       } 
       return true;
    }
}
// 내 코드와 유사한 방식

회고:
이 문제도 그렇게 어려운 문제는 아니었던 것 같다.
다만 처음에 잠시 역순으로 진행하면 더 편할까 싶은 생각이 들었었는데, 막상 생각해 보니 각 배열에 저장된 정보는 점프라서 정방향이 더 편했다.
간단한 문제라서 쉽게 풀렸지만, 문제를 풀기 시작하기 전에 좀 더 최적의 풀이를 생각해 보고 푸는데에 시간을 투자해야겠다.