LeetCode - Jump Game I

문제 설명

해당 문제는 배열 nums가 주어질 때, nums[i]의 값만큼 현재 i에서 점프를 뛸 수 있다.
위와 같은 상황에서, nums.length-1에 도달할 수 있는가에 대한 문제이다.
도달할 수 있다면 true를 반환하고 아니라면 false를 반환해야 한다.

입력 예시는 다음과 같다.

solution([2, 3, 1, 1, 4]);   // true
solution([3, 2, 1, 0, 4]);   // false

소스 코드

function solution(arr) {
  let last = arr.length - 1; 

  // 배열의 마지막 인덱스부터 루프를 돈다.
  for (let i = last; i >= 0; i--) {
    // 4  ... last === 4
    // 3 ... 3 + 1 >= last(4) ? last = 3
    // 2 ... 2 + 1 >= last(3) ? last = 2
    // 1 ... 1 + 2 >= last(2) ? last = 1
    // 0 ... 0 + 2 >= last(1) ? last = 0
    if (i + arr[i] >= last) {
      // if문의 조건이 참일시, last를 매번 최신화시켜준다.
      // i + arr[i] 가 last 보다 크거나 같다면, arr[i]는 last에 점프가 가능한(도달할 수 있는) 것이다.
      // 즉  i + nums[i]를 통해서 어디까지 점프할 수 있는 지 알 수 있다.
      last = i;
    };
  };
  // last 값이 0 이라면 배열의 last element까지 점프가 가능한 것이므로 true를 반환한다.
  return last === 0 ? true : false;
}

solution([2, 3, 1, 1, 4]);  // true
// solution([3, 2, 1, 0, 4]);  // false

위 소스 코드의 시간복잡도는 O(n) 이다.

유튜브에 Jump Game의 요구사항에 대해 상세한 설명을 해주는 영상이 있어서
이를 참고하여 문제의 의도를 정확히 이해할 수 있었다.
영상 링크는 다음과 같다.
Youtube | Jump Game