[LeetCode] 45. Jump Game II

질문 자체가 엉망이기 때문에 이해하는데 시간이 좀 걸린 문제이다.

정리해서 요약한 내용은 다음과 같다.

각 배열 요소는 해당 요소에서 얼마나 먼 거리까지 점프할 수 있는지를 수로 나타내는 값이다.
요소의 마지막까지 도달하는데 필요한 최소 점프 수를 반환해라
※ 인덱스는 0부터 시작한다.

😎풀이

function jump(nums: number[]): number {
    if (nums.length === 1) return 0;
    
    let jumps = 0;  // 총 점프 횟수
    let currentMax = 0;  // 현재 점프로 도달할 수 있는 최대 인덱스
    let nextMax = 0;  // 다음 점프로 도달할 수 있는 최대 인덱스
    
    for (let i = 0; i < nums.length - 1; i++) {

        // i + nums[i] = 해당 인덱스를 밟고 점프할 수 있는 최대 거리
        nextMax = Math.max(nextMax, i + nums[i]);
        
        // 이전에 밟았던 최대 거리까지 왔다면 다음 점프
        if (i === currentMax) {
            jumps++;  // 점프 횟수 증가
            currentMax = nextMax;  // 다음 점프의 최대 도달 범위로 갱신
            
            // 다음 점프로 마지막 인덱스에 도달할 수 있으면 종료
            if (currentMax >= nums.length - 1) {
                break;
            }
        }
    }
    
    return jumps;
}