Leetcode Java Jump Game II

문제

Link

코드

class Solution {

  public int jump(int[] nums) {
    int count = 0;
    int target = 0;
    int max = 0;
    for (int idx = 0; idx < nums.length - 1; idx++) {
      max = Math.max(max, idx + nums[idx]);
      if (idx == target) {
        count++;
        target = max;
      }
      if (target == nums.length - 1) {
        break;
      }
    }
    return count;
  }

}

결과

Link

설명

1. 최소의 점프로 배열의 마지막 자리에 도달하기 위한 횟수를 구하는 문제이다.

2. 반복을 통해서 마지막 자리에 도달하기 위한 최소 점프 횟수를 구한다.
   • 목표가 되는 지점이 가장 먼 지점으로 갈 수 있는 max를 구하기 위해 max와 점프 길이인 idx + nums[idx] 중 큰 값을 max에 주입한다.
   • idx가 목표 지점인 target인 경우, 점프 횟수인 count를 증가시키고 target에 다음 목표 지점인 max를 주입한다.

3. 목표 지점인 target이 주어진 배열 nums의 마지막 값의 위치인 $nums.length - 1$인 경우, 반복을 종료한다.

4. 반복이 종료되면 점프 횟수인 count를 주어진 문제의 결과로 반환한다.

소스

Sample Code는 여기에서 확인 가능합니다.