45. Jump Game II

난이도: 중간 (Medium)

링크: LeetCode 45

풀이 날짜: 2025/10/15

 

1. 문제 이해

입력: [2,3,1,1,4]
출력: 2
설명: 0 → 1 → 4 로 2번 점프

배열의 각 원소는 해당 인덱스에서 최대 점프할 수 있는 거리를 의미한다.

배열의 시작점(0)에서 출발해 마지막 인덱스에 도달하기 위한 최소 점프 횟수를 구하는 문제다.

 

2. 접근 방식 — Greedy (탐욕적 접근)

이 문제는 모든 경로를 계산할 필요 없이, “한 번의 점프 내에서 도달할 수 있는 최대 범위”를 이용해 해결할 수 있다.

탐욕적으로 생각하면, “현재 위치에서 한 번 점프할 때, 다음 점프의 최대 도달 가능 범위를 최대로 넓히는 선택” 만 반복하면 최소 점프 횟수를 구할 수 있다.

 

이를 위해 다음 세 가지 변수를 사용한다:

변수	의미
farthest	현재까지 탐색 중 도달할 수 있는 가장 먼 인덱스(모든 인덱스에서 업데이트 해줌)
currentEnd	현재 점프 범위의 끝 인덱스 (이 범위를 넘으면 점프해야 함)
jump	지금까지 점프한 횟수

순회 중 매번 farthest를 갱신하면서, 현재 탐색이 currentEnd에 도달했을 때 점프 횟수를 증가시킨다.

 

3. 풀이코드

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
  let farthest = 0;
  let jump = 0;
  let currentEnd = 0;

  // 마지막 칸은 “도착지점”이므로 더 이상 점프 계산 필요 없음 -> i < nums.length - 1
  for (let i = 0; i < nums.length - 1; i++) { 
    farthest = Math.max(i + nums[i], farthest); // 가장 멀리 갈 수 있는 지점
    if (i === currentEnd) {                     // 현재 점프의 끝에 도달
      currentEnd = farthest;                    // 다음 점프 범위 갱신
      jump++;                                   // 점프 횟수 증가
    }
  }

  return jump;
};

이 문제는 “현재 위치에서 갈 수 있는 가장 먼 곳”만 고려해도 되는 구조다.

그 이유는, 한 번의 점프 범위 안에서는 어디서 점프하든 다음 점프의 최대 도달 범위가 같다는 점 때문이다.

 

즉, 어떤 칸에서 점프하든, 그 칸이 현재 점프의 유효 범위(currentEnd) 안에 있다면, 다음 점프 때 고려할 수 있는 “가장 멀리 갈 수 있는 거리(farthest)“는 변하지 않는다. currentEnd 는 farthest 로 업데이트 된다.

 

그래서 탐색 중 i === currentEnd 가 되는 시점은 “현재 점프 범위가 끝났다”는 뜻이다. 이때 다음 점프를 해야만 더 멀리 갈 수 있으므로, 점프 횟수를 1회 증가시키고, currentEnd 를 farthest 로 업데이트 한다.

 

예시 시나리오

nums = [2, 3, 1, 1, 4] 라고 하면, 

단계	i	nums[i]	farthest	currentEnd	jump	설명
시작	0	2	2	0	0	0에서 최대 2칸까지 갈 수 있음
점프1	0→2			currentEnd=2	jump=1	첫 점프 범위(0~2)
탐색중	1	3	4	2	1	i=1에서 farthest=4 (다음 점프 시 4까지 가능)
점프2	2	1	4	2	1→2	i가 currentEnd(2)에 도달 → 새로운 점프 필요

즉, i === currentEnd 가 되는 시점은 “지금 점프한 범위의 끝까지 왔으니, 다음 점프를 시작해야 하는 타이밍”을 의미한다. 이 시점에만 점프를 늘리면, 쓸데없는 중복 점프 없이 최소 횟수로 끝까지 도달할 수 있다.

시간 및 공간 복잡도

• 시간 복잡도: O(n) — 배열을 한 번만 순회
• 공간 복잡도: O(1) — 추가 공간 거의 없음

 

4. 핵심 정리

개념	설명
문제 유형	Greedy, 배열
핵심 변수	farthest, currentEnd, jump
핵심 아이디어	각 점프 구간 내에서 최대로 도달 가능한 지점을 추적
복잡도	시간 O(n), 공간 O(1)
포인트	“점프 시점”은 탐색 중 i === currentEnd일 때 결정된다