Jump Game

💬 문제

[문제 링크]
int 배열 nums가 주어지고 각 인덱스의 값은 이동할 수 있는 최대 거리
인덱스 0에서부터 출발해서 마지막 인덱스에 도착할 수 있는가
가능하다면 true, 불가능하다면 false 반환

✍️ 나의 풀이

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
    if (nums.length > 1 && nums[0] === 0)
        return false;
    let goal = nums.length - 1;
    for (let i = nums.length - 2; i >= 0; i--) {
        if (i + nums[i] >= goal)
            goal = i;
    }
    return goal === 0;
};

마지막 인덱스 이전부터 시작하여 해당 인덱스 번호에 값을 더했을 때 목적지(처음에는 마지막 인덱스 번호)에 도착할 수 있는지 확인
가능하다면 일단 거기까지만 도착하면 되니까 목적지 번호를 바꿔줌
거꾸로 내려가서 0까지 도착한 다음 목적지가 계속 바뀌어서 0에 도달했다면 마지막 인덱스까지 도착 가능한 것

📌 결과

Accepted
Runtime 61ms (Beats 74.32%)
Memory 52.48MB (Beats 91.57%)

📚 러닝 포인트

이번에도 내 알고리즘이 아니다... 사실 처음에 여러가지 방법을 생각할 때 뒤에서부터 시작해야하지 않을까?라는 실마리는 있었는데 구현해내지는 못했다. 그래서 둘러보던 중 뒤에서부터 목적지를 바꿔가며 가능한지 불가능한지 판단하는 것을 발견! 정말 깔끔했다... 언제쯤 미디엄 레벨 문제를 내 머리로 완성시킬 날이 올까