Leetcode #45 Jump Game II

Writer: Steven, Lee

Date: 12/28, Friday

Purpose: Solving #45 Jump Game II

Level: Hard

Percentage: 26.7% have solved this problem

Time: it took me 1 hour :)

Time Complexity: O(n) worst case

한국어 버전은 밑에 있습니다.

* Caution * Before you read the solution that I used, you need to solve this problem by yourself 

* Description *

Given an array of non-negative integers, 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.

* Example *

Example:

Input: [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.

Note:

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

* What is the Idea? *

There is the one key that we need to recognize to solve it. The key is that we should find out the maximum number to reach the last index in the specific range. Let me give you more detail with this example "nums = [2, 3, 1, 1, 4]". Firstly, we have to start at the first index of the array. so we got nums[0] ("2") which means we are able to stand at nums[2] in the maximum. Then, we go next nums[1]  ("3"). Ohh. . It's bigger than the previous one "nums[0]". so we have to save nums[1] ("3") as the maximum range. Also, we don't reach nums[2] yet so the number of jumps is still 1. Clear. Let's go next again then, we have to check out nums[2] ("1"). It's not bigger than the maximum range that we already saved. Also. It's not the last index where we should reach. Clear. Let's go next again. but It's possible?? Definitely, not. why?? Because obviously, It's out of nums[0] ("2") so we need to know how many steps we can go next. But we know that It's the maximum range nums[1] ("3"). From now on we can go "3" steps from where you are. And also you need to increase the number of jumps which is 2. the range of nums[1] is enough to reach the last index. It's done with "2 jumps steps"

To sum up, 

1. The main point is finding out the maximum number to know how many times we can go next.

2. When it's out of range that you hold on, you need to convert the range to the maximum number that you saved 

3. When it's out of range that you hold on, you need to increase jumps steps.

* Check *

you can check out your answer on this site.

https://leetcode.com/problems/jump-game-ii/

(한국어)

* 난이도는 어려움입니다.

* 오직 26.7%만이 이 문제를 풀었습니다.

* 저는 1시간 정도가 걸렸습니다. ^^/

* 시간복잡도는 최대 O(n)입니다. 

* 주의 *  솔루션을 읽기 전에 스스로 문제를 푸실 수 있어야 합니다.

* 지문 *

음수가 아닌 숫자들로 구성된 배열이 주어진다. 이때 초기 위치로 배열에 가장 첫 번째에 위치하고 있다.

각 배열에 있는 요소는 당신이 갈 수 있는 최대 점프 길이를 의미한다.

당신의 목표는 최소한의 점프로 마지막 위치에 가야 하는 것이다.

* 예시 *

Example:

Input: [2,3,1,1,4]
Output: 2
설명: 마지막 인덱스에 갈 수 있는 최소한의 점프 수는 2이다.
 점프 첫 번째 점프는 인덱스 0에서 1까지이다. 그리고 3개로 마지막 인덱스까지 점프한다.

Note:

언제나 마지막 인덱스까지 갈 수 있다고 가정한다.

* 아이디어 *

우리가 이 문제를 풀기 위해서 꼭 알아야 하는 부분이 있습니다. 그것은 특정한 범위에서 마지막 위치까지 가기 위한 최대 숫자를 찾아야 하는 것입니다. "nums = [2, 3, 1, 1, 4]"로 주어졌을 때를 가정해서 좀 더 상세히 설명하겠습니다. 첫 번째로 우리는 항상 맨 처음 위치에서 시작합니다. 그러면 최대로 갈 수 있는 거리가 "2"인 nums[0] ("2")를 얻을 수 있겠네요. 그리고 다음으로 넘어가보면 nums[1] ("3")이 있습니다. 오. . 전에 있는 "nums[0]"보다 값이 더 크네요 그러면 우리들은 이 nums[1] ("3")을 최대 범위로 저장을 해야 합니다. 또한 우리는 아직 nums[2]까지 도달하지 못했기 때문에 여전이 점프 수는 하나입니다. 여기까지는 확실하네요. 다음으로 가보겠습니다. 그러면 우리들은 또 다시 nums[2] ("1)를 체크해야 합니다. 하지만 이것은 우리들이 이미 저장한 값보다 크지는 않습니다. 그리고 아직 마지막까지 도착하지 못했습니다. 여기까지도 분명하네요. 다음으로 가보겠습니다. 하지만 갈 수 있나요? 명백하게 할 수 없습니다. 왜 그럴까요?? 왜냐하면 범위가 nums[0] ("2")를 넘어갔습니다. 그러기 때문에 우리들은 얼마만큼 다음으로 갈 수 있는지를 알아야 합니다. 하지만 우리는 이미 최대의 범위가 nums[1] ("3")이라고 알고 있습니다. 지금 있는 곳부터 "3" 점프까지 갈 수가 있겠네요. 그리고 이때 점프 수는 2개로 증가합니다. nums[1] ("3")은 이미 마지막 위치까지 충분히 갈 수 있습니다. 그래서 "2개의 점프"로 끝나겠네요

 요약해보면,

1. 주요한 부분은 얼마만큼 갈 수 있는지를 알기 위해 최대 숫자를 찾아야 합니다.

2. 만약 지금 현재 지정한 범위보다 위치가 초과하면, 그 범위를 이미 지정했던 최대 숫자로 교체합니다.

3. 만약 지금 현재 지정한 범위보다 위치가 초과하면, 점프 수를 증가시킵니다.

* Check *
이 사이트에서 정답의 유무를 확인하실 수 있습니다.

https://leetcode.com/problems/jump-game-ii/

Code & 코드

You need to read the code by yourself

스스로 코드를 읽을 줄 알아야 합니다.

public class JumpGameII_45{
    public static int jump(int[] nums) {
        
        if(nums.length <= 1) return 0;
        
        int index = 1;
        int past = nums[0];
        int max = nums[0];
        
        if(past >= nums.length - 1) return 1;
 
        for(int i = 1; i < nums.length ; i++){
            if(nums[i]+i >= max) max = nums[i]+i;
            if(max >= nums.length - 1){
                index++;
                break;
            }
            if(past == i){
                past = max;
                index++;
            }
        }
        return index;
    }
    public static void main(String args[]){
        int[] nums = {2, 1, 1, 3, 4};
        int result = jump(nums);
        System.out.println("Result: " + result);
    }
}