LeetCode - 점프 게임 II

문제 설명

음수가 아닌 정수 nums의 배열이 주어지면 초기에 배열의 첫 번째 인덱스에 배치됩니다.

배열의 각 요소는 해당 위치에서의 최대 점프 길이를 나타냅니다.

귀하의 목표는 최소 점프 횟수로 마지막 인덱스에 도달하는 것입니다.

항상 마지막 색인에 도달할 수 있다고 가정할 수 있습니다.

문제 진술 출처: https://leetcode.com/problems/jump-game-ii/

예 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.

예 2:

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

제약:

- 1 <= nums.length <= 10^4
- 0 <= nums[i] <= 1000

설명

문제는 이전 블로그 게시물Jump Game의 확장입니다. 점프 게임 문제에서 배열의 마지막 인덱스에 도달할 수 있는지 여부를 계산해야 했습니다. 이 문제에서는 최소 점프 수를 계산해야 합니다.

무차별 대입 방식

순진한 접근 방식은 재귀를 사용하여 문제를 해결하는 것입니다. 이 재귀의 기본 사례는 마지막 인덱스에 도달할 때 발생합니다.

첫 번째 요소에서 도달할 수 있는 모든 요소를 ​​재귀적으로 호출합니다. 즉, 재귀 스택의 모든 분기를 탐색하고 마지막 인덱스에 도달하기 위한 최소 점프 수를 반환합니다.

이 접근 방식의 C++ 스니펫은 다음과 같습니다.

int minJumps(vector<int> &nums, int index){
    if(index >= nums.size() - 1)
        return 0;

    int jumps = INT_MAX;

    for(int index = index + 1; i <= index + nums[index]; i++)
        jumps = min(jumps, 1 + minJumps(nums, i));

    return jumps;
}

위 방법의 시간 복잡도는 O(2^N)이고 공간 복잡도는 O(1)입니다.

동적 프로그래밍

동적 프로그래밍을 사용하면 시간 복잡도를 O(N^2)로 줄일 수 있습니다. 순진한 접근 방식에는 겹치는 하위 문제가 있으며 그 결과는 배열에 저장됩니다. 노드의 최소 점프를 계산할 때 결과가 저장된 배열에 있는지 여부를 확인합니다.

이 접근 방식의 C++ 스니펫은 다음과 같습니다.

int jump(vector<int>& nums) {
    int n = nums.size();
    vector<int> store(n);
    store[0] = 0;

    for(int i = 1; i < n; i++) {
        store[i] = INT_MAX;

        for(int j = 0; j < i; j++) {
            if(i <= nums[j] + j && store[j] != INT_MAX){
                store[i] = min(store[i], store[j] + 1);
                break;
            }
        }
    }

    return store[n - 1];
}

위 방법의 시간 복잡도는 O(N^2)이고 공간 복잡도는 O(n)입니다.

최적의 탐욕스러운 접근법

이 접근 방식에서는 각 단계에서 최적의 선택을 하는 그리디 알고리즘을 사용합니다. 어떤 지수에서든 마지막 지수에 가까워질 다음 단계를 결정합니다.

먼저 알고리즘을 확인해 봅시다.

- set count, current, farthest = 0, 0, 0

- if nums[0] == 0 || nums.length == 1
  - return 0

- loop for i = 0; i < nums.length; i++
  - if nums[i] + i > farthest
    - set farthest = nums[i] + i

  - if i == current
    - increment count: count++
    - current = farthest

- for end

- return count

C++, Golang, Javascript에서 우리의 솔루션을 확인해 봅시다.

C++ 솔루션

class Solution {
public:
    int jump(vector<int>& nums) {
        int count = 0, current = 0, farthest = 0;

        if(nums[0] == 0 || nums.size() == 1) {
            return 0;
        }

        for(int i = 0; i < nums.size() - 1; i++) {
            if(nums[i] + i > farthest) {
                farthest = nums[i] + i;
            }

            if(i == current) {
                count++;
                current = farthest;
            }
        }

        return count;
    }
};

골랑 솔루션

func jump(nums []int) int {
    count, current, farthest := 0, 0, 0

    if nums[0] == 0 || len(nums) == 1 {
        return 0
    }

    for i := 0; i < len(nums) - 1; i++ {
        if nums[i] + i > farthest {
           farthest = nums[i] + i
        }

        if i == current {
            count++
            current = farthest
        }
    }

    return count
}

자바스크립트 솔루션

var jump = function(nums) {
    let count = 0, current = 0, farthest = 0;

    if(nums[0] == 0 || nums.length == 1) {
        return 0;
    }

    for(let i = 0; i < nums.length - 1; i++) {
        if(nums[i] + i > farthest) {
            farthest = nums[i] + i;
        }

        if(i == current) {
            count++;
            current = farthest;
        }
    }

    return count;
};

주어진 입력에 대해 알고리즘을 연습해 봅시다.

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

Step 1: count = 0
        current = 0
        farthest = 0

Step 2: if nums[0] == 0 || nums.length == 1
           2 == 0 || 5 == 1
           false

Step 3: loop for i = 0; i < nums.length - 1; i++
          i < nums.length - 1
          0 <  5 - 1
          0 < 4
          true

          if nums[i] + i > farthest
             nums[0] + 0 > 0
             2 + 0 > 0
             true

             farthest = nums[i] + i
                      = 2

          if i == current
             0 == 0
             true

             count++
             count = 1

             current = farthest
                     = 2

          i++
          i = 1

Step 4: loop for i < nums.length - 1
          i < nums.length - 1
          1 <  5 - 1
          1 < 4
          true

          if nums[i] + i > farthest
             nums[1] + 1 > 2
             3 + 1 > 2
             true

             farthest = nums[i] + i
                      = 4

          if i == current
             1 == 2
             false

          i++
          i = 2

Step 5: loop for i < nums.length - 1
          i < nums.length - 1
          2 <  5 - 1
          2 < 4
          true

          if nums[i] + i > farthest
             nums[2] + 2 > 4
             1 + 2 > 4
             false

          if i == current
             2 == 2
             true

             count++
             count = 2

             current = farthest
                     = 4

          i++
          i = 3

Step 6: loop for i < nums.length - 1
          i < nums.length - 1
          3 <  5 - 1
          3 < 4
          true

          if nums[i] + i > farthest
             nums[3] + 3 > 4
             1 + 1 > 4
             false

          if i == current
             3 == 4
             false

          i++
          i = 4

Step 7: loop for i < nums.length - 1
          i < nums.length - 1
          4 <  5 - 1
          4 < 4
          false

Step 8: return count

We return the answer as 2.