LeetCode - Jump Game II (Javascript)

문제 설명

배열의 끝에 다다를 수 있는 최소 점프 횟수를 구하면 되는 문제다.
배열 안의 모든 수는 자연수다.

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

You can assume that you can always reach the last index.

Example 1:

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [2,3,0,1,4]
Output: 2

Constraints:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 1000

---

소스코드

function jump(nums) {
  let sectionMax = 0;
  let endPoint = 0;
  let count = 0;
  for (let i = 0; i < nums.length - 1; i++) {
    sectionMax = Math.max(sectionMax, i + nums[i]);
    if (i === endPoint) {
      count++;
      endPoint = sectionMax;
    }
  }
  return count;
}

---

풀이 설명

처음에는 재귀 방식을 사용해서 모든 경우의 수를 다 탐색해보려 했었다…
하지만 시간복잡도 때문에 코드가 통과되지 않아, 결국 일반 반복문을 통한 해결 방법을 찾아냈다.

위와 같은 배열이 주어졌다고 가정하고 풀이를 설명해보도록 하겠다. 이 풀이과정의 핵심은 아래와 같다.

---

1. 요소와 요소 간의 점프가 아닌, 구역과 구역 간의 점프라고 생각해야 한다.
2. 구역(section) 내에서 뛸 수 있는 최대 거리를 뛴다.

---

구역과 구역 간의 점프라는 것이 와닿지 않을 수도 있는데, 아래 그림을 통해 설명해보도록 하겠다.

우선, 시작점은 위의 사진과 같이 첫 번째 배열인 2에서 시작한다(i=0). 그리고 endPoint는 구역의 끝을 의미하는데, 우리는 endPoint에서 점프를 수행한다. 그리고 점프를 수행할 때에는 반드시 구역 내에서 최대로 점프할 수 있는 거리만큼을 점프한다.

따라서 현재 구역은 2(i=0) 한 칸이고, 최대로 뛸 수 있는 거리는 2이기 때문에 endPoint를 2로 설정해준다. 그리고, endPoint는 현재 위치에서의 상대적 거리가 아닌, 배열 전체에서의 절대적 거리를 구해야 한다. 따라서 sectionMax를 구할 때, 단순히 배열의 값(nums[i])을 집어넣는 것이 아닌, i + nums[i]를 해줘야 정확한 endPoint를 구할 수 있다. 하지만 위의 경우는 아직 i=0이기 때문에 0+2가 되어 다음 섹션의 endPoint는 2가 될 것이다.

그리고 아직 sectionMax는 2다. (점프를 했다고 초기화시켜주지 않음)

이후에 섹션 간의 점프를 통해 다음 섹션 인덱스 1~2로 넘어간다 (점프를 했기 때문에 count는 1추가된 상황). 그리고 이 섹션 안에서 순회를 하며 최대값을 계속 갱신해준다.

sectionMax = (1+3);

sectionMax = (1+3) vs (2+1) === 4

그러면 이 섹션 안에서의 sectionMax는 4이기 때문에, 반복문에 의해 i가 endPoint인 2에 닿았을 때 또 다시 sectionMax의 위치까지 점프를 할 것이다.

그러면 반복문은 다음 endPoint인 i=4까지 순회를 할 것인데, 반복문 자체 조건문 i < nums.length - 1에 의해 반복문은 중간에 종료가 될 것이다. 따라서 현재까지 점프를 한 횟수(count)는 총 2회로, 2가 반환된다.

정리를 해보자면, 매 섹션마다 해당 섹션 내에서 가장 멀리 뛸 수 있는 숫자를 고른다(sectionMax). 그리고 endPoint를 통해 그 최대거리 내의 section에서 또 최대 점프거리를 탐색한다. 이런 식으로 구역마다 최대거리를 골라서 그 만큼 점프를 계속 할 수 있도록 하는 것이다.

---