LeetCode - Jump Game I (Javascript)

문제 설명

이번에는 이전 점프게임과는 다르게, 주어진 배열의 요소들을 통해 종료 지점 (배열의 끝)까지 도달할 수 있는지 없는지를 판별하는 문제다.

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

---

소스 코드 (첫 시도)

첫 시도에는 그냥 간단하게 재귀를 통한 탐색을 시도했다..
하지만 테스트케이스에 말도 안되게 긴 배열이 들어있었기에, 시간초과로 통과되지 못했다ㅜ

function canJump(nums, idx = 0) {
  if (idx >= nums.length - 1) return true;
  for (let i = nums[idx]; i > 0; i--) {
    if (canJump(nums, idx + i)) return true;
  }
  return false;
}

---

소스 코드 (시간복잡도 고려)

한 번 순회를 했는데 false가 리턴됐으면, 해당 num은 아예 건너 뛰도록 0을 할당해줬다.
그리고 조건문에 nums[idx]가 0이면 바로 false가 return되도록 추가했다. (실패했던 방문을 반복할 필요가 없어짐)

function canJump(nums, idx = 0) {
  if (idx >= nums.length - 1) return true;
  if (!nums[idx]) return false;
  for (let i = 1; i <= nums[idx]; i++) {
    if (canJump(nums, idx + i)) return true;
    nums[idx + i] = 0;
  }
  return false;
}

근데… 코드 자체는 통과는 됐지만, 시간복잡도가 하위 8퍼센트를 웃돈다…

---

소스 코드 (최종)

물론 통과가 되긴 했지만, 더 나은 효율성을 갖는 로직은 없을까 고민을 많이 해봤다.
그러다가 유튜브에 올라온 솔루션 중, max값을 활용한 굉장히 좋은 코드를 발견했다.

이 코드는 재귀가 아닌 단순 반복문을 사용한다.

function canJump(nums) {
  let max = 0; // 현재 위치에서 갈 수 있는 최대 거리
  for (let i = 0; i < nums.length; i++) {
    // i가 max보다 크면, i는 max를 지나친 것이기에 이 max가 이 배열에서 갈 수 있는 최대 거리다.
    // 따라서 i까지 점프가 불가능 하기에 return false를 해주면 된다.
    if (i > max) return false;
    if (i + nums[i] >= nums.length - 1) return true; // 현재 i + 뛸 수 있는 거리 >= 종착점이면 return true를 해주면 된다.
    max = Math.max(max, i + nums[i]); // 최대 어디까지 점프 할 수 있는지 매 반복마다 값을 갱신
  }
}

시간 효율성과 공간 효율성 모두가 대폭 상승된 모습이다.
이런 로직을 단번에 떠올릴 수 있도록 더 연습을 많이 해야겠다..

로직 설명

[3,2,1,0,4]의 경우를 예시로 들어 설명해보도록 하겠다.

우선 첫 시작에는 max가 0으로 기본 할당 되어있다. 그리고 위와 같이 시작점에서 가장 멀리 갈 수 있는 거리는 index = 3까지다. 이제 계속 순회를 하며 최대값을 갱신해주면 된다.

하지만 다음 index에서도 여전히 max는 3이다(index).

또 여전히 max는 3이다.

그리고 마지막으로 0에서는 다음으로 건너가지 못하기 때문에, i는 4에 닿게되고, i > max(4 > 3)이 성립돼 false가 반환된다. 각 요소별로 갈 수 있는 최대 거리만 계속 Math.max를 통해 구해주면서, i값과 비교를 통해 도달 가능 여부를 판단하면 되는 문제였던 것이다.

---