문제 설명

Jump Game - LeetCode

주어진 정수 배열 nums에서 각 인덱스에서 점프할 수 있는 최대 거리가 nums[i]로 주어질 때,
배열의 첫 번째 인덱스에서 마지막 인덱스로 도달할 수 있는지 여부를 판단하는 문제입니다.

✅ 제약 조건

  • 1 ≤ nums.length ≤ 10⁴
  • 0 ≤ nums[i] ≤ 10⁵
  • O(N) 이하의 시간 복잡도로 해결하는 것이 바람직

✅ 출력 값

  • 마지막 인덱스에 도달할 수 있으면 True, 도달할 수 없으면 False

해설

1️⃣ 동적 계획법 (DP, O(N²)) → 비효율적

  • dp[i] = True이면 해당 위치에서 도달 가능하다는 의미
  • 각 인덱스에서 가능한 점프를 모두 확인하여 dp 배열 업데이트
  • 시간 복잡도 O(N²) → 입력 크기가 크면 비효율적

2️⃣ 그리디 알고리즘 (O(N)) [추천]

  • 현재까지 도달할 수 있는 최대 거리(maxReach)를 갱신
  • 현재 인덱스(i)가 maxReach보다 크면 도달 불가 → False 반환
  • 도달 가능하면 True 반환
  • 시간 복잡도 O(N) (배열을 한 번만 순회)
  • 공간 복잡도 O(1) (추가 배열 사용 X)

코드 풀이

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def canJump(nums):
    maxReach = 0  # 현재 도달할 수 있는 최대 거리

    for i in range(len(nums)):
        if i > maxReach:  # 현재 인덱스에 도달할 수 없으면 False
            return False
        maxReach = max(maxReach, i + nums[i])  # 최대 도달 거리 갱신
        if maxReach >= len(nums) - 1:  # 마지막 인덱스에 도달 가능하면 True
            return True

    return True

Javascript

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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]);
        if (maxReach >= nums.length - 1) return true;
    }

    return true;
};

참고 및 출처

programmers Coding Test
LeetCode - The World’s Leading Online Programming Learning Platform