[JavaScript]45. Jump Game II

45. Jump Game II

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

 

Example 3: 

 

 

계획

array에 위치한 숫자는 그자리에 도착했을때 그자리에서 움직일수있는 칸수입니다. 그리고 가장 빠른 경로를 찾으면됩니다. 

 

그리고 앞으로 이동할때는 두가지 선택이있습니다. 그냥 한칸 움직이거나, 그 위치에 있는 숫자만큼 움직일수있습니다.

 

가장 빠른 경로를 찾는게 이 문제에서 찾아야하는 것입니다. 

 

 

구현 전략

2에서 시작하고 2의 레벨을 0이라 생각합니다. 그리고, 2에서 갈수있는 2가지 경로 3 과 1 을 레벨 1로 생각합니다. 그리고 다음레벨에 있는 1과 4가 레벨 2라 지정하면, 우리는 2번에 끝까지 도달할수있는 것을 알수있습니다. 

 

BFS와 유사한 성격을 가졌다고 할수있습니다. 

 

 

 

해설

var jump = function(nums) {
	if(nums.length === 1) return 0;  //우선 length가 1이면 점프가 필요없습니다. 
	let jumps = 0; //점프의 시작은 0으로 시작합니다. 
	let maxReach = nums[0]; // 지금까지 최대로 도달한위치
	let steps = nums[0]; //현재 위치
	for(let i = 1; i < nums.length - 1; i++){
		maxReach = Math.max(maxReach, i + nums[i]) //현재 최대로 도달한위치와 
		steps--; //
		if(steps === 0){
			jumps++;
			steps = maxReach - i;
		}
	}
	return jumps + 1;  
};