55. Jump Game

난이도: 중간 (Medium)

링크: LeetCode 55

풀이 날짜: 2025/10/15

 

 

1. 문제 이해

각 인덱스의 값은 그 위치에서 최대 몇 칸까지 점프할 수 있는지를 의미한다.

배열의 시작점에서 출발해 마지막 인덱스까지 도달 가능한지 여부를 true 또는 false로 반환하는 문제다.

 

예시:

입력: [2,3,1,1,4]
출력: true   // 0→1→4 로 이동 가능

입력: [3,2,1,0,4]
출력: false  // 인덱스 3에서 멈춤

 

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

이 문제는 모든 가능한 경로를 탐색할 필요가 없다. 중요한 건 “지금 위치에서 갈 수 있는 가장 먼 거리”가 어디인지뿐이다.

 

즉, 매 순간 현재까지 내가 도달할 수 있는 가장 멀리 있는 지점이 어디인가만 추적하면 된다. 이 접근이 Greedy(탐욕적)인 이유는, 매 단계에서 “가장 유리한 선택(= 가장 멀리 갈 수 있는 선택)”만 고려해도 결국 전체 문제를 해결할 수 있기 때문이다.

 

예를 들어,[2,3,1,1,4]에서 처음 위치(0)에서는 2칸까지 이동할 수 있다. 다음 인덱스(1)로 가면 3칸을 더 갈 수 있으므로, ‘지금까지 갈 수 있는 가장 먼 거리’는 1 + 3 = 4가 된다. 이 순간, 이미 배열 끝에 도달할 수 있다는 사실이 결정된다.

따라서 “모든 점프 조합”을 고려하지 않아도 “현재 최대로 도달 가능한 범위”만 추적하면 충분하다.

 

3. 풀이코드

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {    
  let farthest = 0;
  
  for (let i = 0; i < nums.length; i++) {  
    if (i > farthest) return false;               // 현재 위치조차 도달 불가능
    farthest = Math.max(farthest, nums[i] + i);   // 가장 먼 거리 갱신
    if (farthest >= nums.length - 1) return true; // 마지막까지 도달 가능
  }
};

 

• 시간 복잡도: O(n) — 한 번의 순회로 끝
• 공간 복잡도: O(1) — 추가 메모리 거의 없음

 

4. 핵심 정리

개념	설명
핵심 아이디어	“현재까지 도달 가능한 최대 거리”를 추적한다
왜 Greedy인가	매 순간 가능한 최선(가장 멀리 가는 선택)을 하면 전체 최적 결과가 보장된다
효율성	DP보다 빠르고, 중복 계산이 없음
실패 조건	현재 인덱스가 도달 가능한 거리보다 클 경우 → 즉시 false