[LeetCode Medium] Jump Game JavsScript

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

문제 설명

nums = [2,3,1,1,4] 같이 number의 배열이 주어진다. 각각의 숫자는 현재 index부터 최대 몇칸까지 이동할 수 있는지를 나타낸다. 예를들어 index 0 의 값은 2이기 때문에 1칸 또는 2칸 이동할 수 있고, index 1의 값은 3이기 때문에 1,2,3 중에 이동할 수 있다.
그래서 마지막 index 또는 넘어까지 갈 수 있는지 확인 하는 문제이다.

문제 풀이

난 처음에 재귀로 풀었었다. 거의 dfs 느낌으로 하나하나 다 돌았는데 예제는 다 맞았지만 엄청나게 많은 원소가 들어있는 테스트에서는 시간초과가 떴다.

생각을 하다 잘 모르겠어서 다른 사람의 풀이를 봤는데 이게 웬걸... 너무 쉽게 푸는 것... 코드를 보고 이해했다..

최대 어디까지 갈 수 있는지 max값을 지정해 두는게 중요하다.. O(n)으로도 풀 수 있었다. 생각만 잘하면 코드는 쉬운 문제 ㅠ

코드

var canJump = function(nums) {
    let max = 0; // 갈 수 있는 최대값.
    
    for (let i = 0; i < nums.length; i++) {
        if (i > max) return false; // i가 이 최대값 보다 크다면 i는 도달하지 못 하는 곳이다. false를 반환.
        
        if (i + nums[i] >= nums.length - 1) return true; // 현재 index + index의 값을 더했을 때 nums의 길이를 넘어가면 true!
            
        max = Math.max(max, i + nums[i]); // 최대 어디까지 갈 수 있는지 max 값을 갱신.
    }
};