질문

이 기사에서는 Leetcode의 '55. Jump Game' 질문을 다룰 것입니다. 이 질문은 고전적인 문제입니다. 관점에 따라 Greedy Algorithm 문제 또는 Dynamic Programming 문제입니다.

의문:

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.
Return true if you can reach the last index, or false otherwise.

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

질문 설명

이 질문의 등급은 보통입니다. Greedy Algorithm 기술을 사용하는 경우 정확하다고 말할 수 있습니다. Dynamic Programming 기법을 사용하는 경우 이 질문은 어려움으로 간주될 수 있습니다. 이 질문에서는 Greedy Algorithm 기법을 사용합니다.

우리가 요청받은 것은 인덱스 0에서 배열의 마지막 인덱스로 점프하는 것입니다. 여기서 각 인덱스는 점프할 수 있는 거리를 나타냅니다. 따라서 값이 2인 인덱스에 있는 경우 2개의 인덱스를 앞으로 이동할 수 있습니다(또는 원하는 경우 1개). 처음에는 이 문제가 사소해 보이고Brute Force 모든 경로가 마지막 색인에 도달하면 완료된 것입니다. 이것은 거의 그래프 문제입니다. 그러나 이것은 이 문제를 해결하는 가장 효율적인 방법은 아닙니다. O(n^n) 시간입니다. 매우 느립니다.

대신, 우리는 Greedy으로 가고 이 O(n) 시간을 수행합니다.

권장 지식

Array

Greedy Algorithm

Big O Notation

우리는 무엇을 알고 있습니까?

음수가 아닌 정수 배열이 주어졌습니다.

각 index는 점프할 수 있는 거리를 나타내며 마지막 인덱스로 점프해야 합니다.

어떻게 할 것인가:

처음에는 '인덱스 0부터 시작해서 마지막 인덱스에 도달할 때까지 계속 점프하고 유효하지 않은 경로에서 역추적합니다.'라고 생각할 수 있습니다. 이것은 Dynamic Programming과 Graph Problem이 매우 유사한 Backtracking 솔루션인 Brute Force 솔루션입니다.

대신 인덱스 0에서 시작하는 대신 논리를 반대로 할 것입니다. 마지막 인덱스에서 시작하지 않는 이유는 무엇입니까? 처음에는 마지막 인덱스인 골 포스트를 갖게 되며 골 포스트의 목표는 인덱스 0에 도달하는 것입니다. '이 요소가 골 포스트로 이동할 수 있습니까?'라고 묻는 배열을 거꾸로 반복합니다. 그렇다면 해당 요소는 점프할 수 있기 때문에 새 골 포스트가 됩니다. 우리는 전체 배열을 살펴볼 때까지 이 작업을 계속합니다. 첫 번째 인덱스에 도달했다면 마지막 인덱스로 점프할 수 있고, 그렇지 않으면 점프할 수 없습니다.

초기에 마지막 인덱스인 골 포스트를 초기화할 것입니다.

배열을 거꾸로 반복하는 For 루프를 설정할 것입니다.

각 요소에 '여기에서 골대 위로 점프할 수 있습니까?'를 묻습니다. 그렇다면 목표 포스트를 해당 요소로 설정합니다.

그렇지 않은 경우 계속 반복합니다.

전체 배열을 살펴볼 때까지 이 논리를 반복합니다.

이제 골 포스트가 첫 번째 인덱스에 있습니까? 그렇다면 마지막 인덱스로 이동할 수 있고 그렇지 않으면 이동할 수 없습니다.

빅오 표기법:

시간 복잡도: O(n) | 여기서 n은 배열의 길이입니다.

공간 복잡도: O(1) | 추가 메모리를 할당하지 않기 때문입니다.

파이썬 솔루션

class Solution:
    def canJump(self, nums: List[int]) -> bool:

        goal_post = len(nums) - 1

        for i in range(len(nums) - 2, -1, -1):
            if i + nums[i] >= goal_post:
                goal_post = i

        return (goal_post == 0)

자바 솔루션

class Solution {
    public boolean canJump(int[] nums) {

        int goal_post = nums.length - 1;

        for (int i = nums.length - 1; i >= 0; i--) {
            int jump_distance = i + nums[i];
            if (jump_distance >= goal_post) {
                goal_post = i;
            }
        }

        return (goal_post == 0) ? true : false;
    }
}

C++ 솔루션

class Solution {
public:
    bool canJump(vector<int>& nums) {

        int goal_post = nums.size() - 1;

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

        return (!goal_post) ? true : false;
    }
};

자바스크립트 솔루션

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function (nums) {

    let goal_post = nums.length - 1;

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

    return !goal_post ? true : false;
};