Jump Game

[hsskey]

문제 설명 | Jump Game

정수 배열 nums가 주어집니다. 처음에는 배열의 첫 번째 인덱스에 위치하며, 배열의 각 요소는 해당 위치에서 최대 점프 길이
마지막 인덱스에 도달할 수 있으면 true를, 그렇지 않으면 false를 반환

📝 제약조건

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 10^5

💡 예시

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

  • Output: true
  • 설명: 인덱스 0에서 1으로 1단계 점프한 다음, 3단계를 점프하여 마지막 인덱스에 도달

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

  • Output: false
  • 설명: 무엇을 하든 항상 인덱스 3에 도달합니다. 최대 점프 길이는 0이므로 마지막 인덱스에 도달할 수 없음

문제 해결 과정

Step 1: 문제 이해하기

• 작은 예시로 직접 점프 게임 이해하기
  • [2,3,1,1,4]에서:
    • 인덱스 0에서 시작, 최대 2칸 점프 가능 → 인덱스 1 또는 2로 갈 수 있음
    • 인덱스 1로 가면 최대 3칸 점프 가능 → 바로 마지막 인덱스(4)에 도달 가능
  • [3,2,1,0,4]에서:
    • 인덱스 0에서 시작, 최대 3칸 점프 가능 → 어디를 가든 결국 인덱스 3에 도달
    • 인덱스 3의 값은 0이므로 더 이상 점프할 수 없음 → 마지막 인덱스 도달 불가

Step 2: 접근 방법

• 직관적으로 생각하기

  • 처음엔 앞에서부터 접근할 수 있다고 생각하겠지만, 뒤에서부터 접근하는 방식이 효율적
  • 마지막 인덱스에서 시작해 첫 번째 인덱스까지 역순으로 진행
  • 목표 인덱스(goal)에 도달할 수 있는 위치를 계속 업데이트

• 알고리즘 표 작성

goal = 마지막 인덱스 (nums.length - 1)
↓
i = 마지막 인덱스부터 0까지 역순으로 순회
↓
현재 위치(i)에서 nums[i]만큼 점프 가능
↓
i + nums[i] >= goal인지 확인
↓
맞다면 → goal = i (목표 지점 업데이트)
아니면 → 다음 인덱스로 이동
↓
최종적으로 goal이 0이면 성공 (처음부터 끝까지 도달 가능)

Step 3: 코드 설계

1. 목표 인덱스(goal)를 마지막 인덱스로 초기화
2. 마지막 인덱스부터 0까지 역순으로 순회:
   • 현재 위치에서 최대 점프로 목표에 도달 가능한지 확인
   • 가능하다면 목표 위치를 현재 위치로 업데이트
3. 최종적으로 목표가 첫 번째 인덱스(0)인지 확인

Step 4: 코드 구현

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
    // 목표 인덱스를 마지막 인덱스로 초기화
    let goal = nums.length - 1;
    
    // 뒤에서부터 앞으로 순회
    for(let i = nums.length - 1; i >= 0; i--) {
        // 현재 위치에서 점프하여 목표에 도달할 수 있는지 확인
        if(i + nums[i] >= goal) {
            // 가능하다면 목표를 현재 위치로 업데이트
            goal = i;
        }
    }
    
    // 목표가 첫 번째 인덱스라면 성공
    return goal === 0;
};

[hsskey]

Step 2: 접근 방법

• 직관적으로 생각하기

  • 각 위치에서 도달할 수 있는 최대 거리를 계속 추적하는 방식으로 접근
  • 현재 위치가 도달할 수 있는 범위 내에 있지 않다면, 마지막 인덱스에 도달할 수 없음
  • 최대 도달 거리를 계속 갱신하며 배열을 순회

• 알고리즘 표 작성

maxReach = 0 (초기 설정: 최대 도달 가능 거리)
↓
i = 0부터 nums.length-1까지 순회
↓
i > maxReach인지 확인 (현재 위치에 도달할 수 있는지)
↓
yes → false 반환 (도달 불가능)
no → maxReach 갱신: Math.max(maxReach, i + nums[i])
↓
모든 순회 완료 후 true 반환 (마지막 인덱스에 도달 가능)

Step 3: 코드 설계

1. 최대 도달 거리(maxReach)를 0으로 초기화
2. 배열을 순회하면서:
   • 현재 인덱스가 최대 도달 거리보다 크면 false 반환
   • 아니면 maxReach 갱신: Math.max(maxReach, i + nums[i])
3. 모든 순회를 마치면 true 반환

Step 4: 코드 구현

var canJump = function(nums) {
    let maxReach = 0;
    
    for (let i = 0; i < nums.length; i++) {
        if (i > maxReach) return false;
        maxReach = Math.max(maxReach, i + nums[i]);
    }
    
    return true;
};