Jump Game II

[hsskey]

문제 설명 | Jump Game II

정수 배열 nums가 주어질 때, 시작점(인덱스 0)에서 마지막 인덱스(nums[n-1])까지 도달하기 위한 최소 점프 횟수를 구하는 문제. 각 위치 i에서는 최대 nums[i]만큼 앞으로 점프할 수 있다.

📝 제약조건

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 1000
• 항상 마지막 인덱스에 도달할 수 있다고 보장됨

💡 예시

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

  • Output: 2
  • 설명: 인덱스 0에서 1로 1번 점프, 인덱스 1에서 마지막 인덱스로 1번 점프, 총 2번

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

  • Output: 2

문제 해결 과정

Step 1: 문제 이해하기

• 작은 예시로 직접 풀어보기:
  • [2,3,1,1,4]에서:
    • 인덱스 0에서는 1칸 또는 2칸 점프 가능 → 인덱스 1 또는 2로 이동 가능
    • 인덱스 1에서는 최대 3칸 점프 가능 → 인덱스 2, 3, 4로 이동 가능
    • 따라서 0 → 1 → 4로 이동하면 2번의 점프로 도착 가능

Step 2: 접근 방법

• 직관적으로 생각하기

  • 그리디(Greedy) 접근법: 각 지점에서 가장 효율적인 점프를 선택
  • BFS(Breadth-First Search)와 유사한 레벨별 탐색으로 생각할 수 있음

• 알고리즘 표 작성

  초기 상태: result = 0, left = 0, right = 0 (현재 위치 범위)
  ↓
  현재 범위(left ~ right)에서 도달 가능한 가장 먼 위치 찾기
  ↓
  다음 범위 업데이트: left = right + 1, right = 최대도달거리
  ↓
  점프 횟수(result) 증가
  ↓
  마지막 인덱스에 도달할 때까지 반복
  

• 시간 복잡도 고려

  • 각 위치를 최대 한 번씩만 방문: O(n)

Step 3: 코드 설계

1. 결과 변수(result), 현재 범위의 시작(left)과 끝(right) 초기화
2. right가 마지막 인덱스보다 작은 동안 반복:
   • 현재 범위(left~right)에서 도달 가능한 가장 먼 위치(farthest) 계산
   • 다음 범위 업데이트(left = right + 1, right = farthest)
   • 점프 횟수(result) 증가
3. 최종 점프 횟수 반환

Step 4: 코드 구현 및 분석

var jump = function(nums) {
    let result = 0
    let left = 0
    let right = 0

    while(right < nums.length - 1) {
        let farthest = 0
        for(let i = left; i <= right; i++) {
            farthest = Math.max(farthest, i + nums[i])
        }
        left = right + 1
        right = farthest
        result += 1
    }
    return result
};

console.log(jump([2,3,1,1,4]))
console.log(jump([2,3,0,1,4]))