문제 설명

Jump Game II - LeetCode

배열 nums가 주어질 때, 각 인덱스에서 점프할 수 있는 최대 거리가 배열 요소로 주어집니다.
첫 번째 인덱스(0)에서 마지막 인덱스(n-1)로 이동하는 최소 점프 횟수를 구하는 문제입니다.

✅ 제약 조건

  • 항상 마지막 인덱스로 도달할 수 있음 (즉, 도달 불가능한 경우는 없음)
  • 1 ≤ nums.length ≤ 10⁴
  • 0 ≤ nums[i] ≤ 1000

해설

1️⃣ DP (O(N²)) → 비효율적

  • 각 인덱스에서 모든 가능한 점프를 고려하여 최적해를 찾음
  • 시간 복잡도 O(N²) 으로 큰 입력에서 비효율적

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

  • 각 단계에서 최적의 점프 선택 (가장 멀리 갈 수 있는 지점 탐색)
  • 현재 범위 내에서 점프 가능한 최대 위치를 갱신
  • 한 번의 순회(O(N))로 해결 가능

코드 풀이

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def jump(nums):
    n = len(nums)
    jumps = 0  # 점프 횟수
    farthest = 0  # 현재까지 도달할 수 있는 가장 먼 위치
    end = 0  # 현재 점프에서 도달할 수 있는 최대 범위

    for i in range(n - 1):
        farthest = max(farthest, i + nums[i])  # 최대 도달 범위 갱신

        if i == end:  # 현재 범위를 벗어나기 직전이면 점프
            jumps += 1
            end = farthest  # 새로운 점프 범위 설정

    return jumps

Javascript

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

var jump = function(nums) {
    let jumps = 0;
    let farthest = 0;
    let end = 0;

    for (let i = 0; i < nums.length - 1; i++) {
        farthest = Math.max(farthest, i + nums[i]);

        if (i === end) {
            jumps++;
            end = farthest;
        }
    }

    return jumps;
};

참고 및 출처

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