[코딩 테스트] 2026-04-06 — 점프 게임

오늘의 문제 선정 이유

 

물류 최적화와 경로 탐색에 대한 관심이 높아진 오늘, greedy로 빠르게 도달 가능성을 판단하는 점프 게임이 잘 맞습니다.

문제 설명

한 물류 스타트업은 일렬로 놓인 배송 거점을 따라 자동 이동 로봇을 운용합니다.

거점은 0번부터 N-1번까지 있습니다.
각 거점 i에는 정수 jumps[i]가 적혀 있습니다.
이 값은 현재 거점에서 최대 몇 칸까지 앞으로 이동할 수 있는지를 뜻합니다.

로봇은 처음에 0번 거점에 있습니다.
한 번 이동할 때, 1칸 이상 jumps[i]칸 이하로 앞으로 점프할 수 있습니다.

마지막 거점 N-1에 도달할 수 있으면 True, 도달할 수 없으면 False를 출력하세요.

입출력 예시

[text]입력: jumps = [2, 3, 1, 1, 4]
출력: True
설명: 0번에서 1번으로 이동한 뒤, 1번에서 4번으로 점프하면 마지막 거점에 도달할 수 있습니다.

[text]입력: jumps = [3, 2, 1, 0, 4]
출력: False
설명: 3번 거점에서 더 이상 앞으로 갈 수 없습니다. 마지막 거점까지 이어지는 경로가 없습니다.

[text]입력: jumps = [1, 2, 0, 1, 0, 2]
출력: True
설명: 0 -> 1 -> 3 -> 5로 이동하면 마지막 거점에 도달할 수 있습니다.

제약 조건

• 1 <= N <= 100,000

 

• 0 <= jumps[i] <= 100,000

 

• 시간 제한: 1초 내외

 

• 추가 배열 없이 효율적으로 해결하는 것을 권장

풀이 접근법

핵심 아이디어

이 문제는 각 위치에서 갈 수 있는 가장 먼 인덱스를 계속 갱신하면 됩니다.
중요한 점은 "현재 위치에 실제로 도달 가능한가"입니다. 도달 가능한 위치들만 순서대로 보면서 최대로 뻗어 나갈 수 있는 범위를 관리하면, 마지막 인덱스 도달 가능 여부를 빠르게 판단할 수 있습니다.

단계별 풀이 과정

1. maxReach를 만들어 현재까지 도달 가능한 가장 먼 인덱스를 저장합니다.
2. 배열을 왼쪽부터 순회하면서, 현재 인덱스 i가 maxReach보다 크면 그 위치에는 아예 도달할 수 없으므로 False를 반환합니다.
3. 도달 가능한 위치라면 maxReach = max(maxReach, i + jumps[i])로 갱신합니다.
4. 갱신 중 maxReach가 마지막 인덱스 이상이 되면 바로 True를 반환할 수 있습니다.
5. 끝까지 순회해도 막히지 않았다면 마지막 인덱스에 도달 가능한 것이므로 True입니다.

코드 풀이

Python

 

[python]def can_reach_last(jumps):
    n = len(jumps)

    # 길이가 1이면 이미 마지막 위치에 서 있는 상태
    if n == 1:
        return True

    maxReach = 0

    for i in range(n):
        # 현재 위치까지 못 왔다면 이후도 볼 필요가 없음
        if i > maxReach:
            return False

        # 현재 위치에서 갈 수 있는 최대 거리 반영
        maxReach = max(maxReach, i + jumps[i])

        # 마지막 인덱스 이상 도달 가능하면 종료
        if maxReach >= n - 1:
            return True

    return True


# 예시 실행
print(can_reach_last([2, 3, 1, 1, 4]))  # True
print(can_reach_last([3, 2, 1, 0, 4]))  # False
print(can_reach_last([1, 2, 0, 1, 0, 2]))  # True

JavaScript

 

[javascript]function canReachLast(jumps) {
  const n = jumps.length;

  // 길이가 1이면 이미 마지막 위치에 있음
  if (n === 1) {
    return true;
  }

  let maxReach = 0;

  for (let i = 0; i < n; i++) {
    // 현재 위치에 도달할 수 없으면 실패
    if (i > maxReach) {
      return false;
    }

    // 현재 위치에서 갈 수 있는 최대 거리 갱신
    maxReach = Math.max(maxReach, i + jumps[i]);

    // 마지막 인덱스 이상 도달 가능하면 성공
    if (maxReach >= n - 1) {
      return true;
    }
  }

  return true;
}

// 예시 실행
console.log(canReachLast([2, 3, 1, 1, 4])); // true
console.log(canReachLast([3, 2, 1, 0, 4])); // false
console.log(canReachLast([1, 2, 0, 1, 0, 2])); // true

시간·공간 복잡도

• 시간 복잡도: O(N) — 배열을 한 번만 순회합니다.

 

• 공간 복잡도: O(1) — 추가 자료구조 없이 변수만 사용합니다.

틀리기 쉬운 포인트

• jumps[i]가 0이어도 바로 실패가 아닙니다. 그 위치가 마지막 인덱스일 수도 있고, 이미 그 전 단계에서 더 멀리 도달 가능할 수도 있습니다.

 

• i > maxReach 조건을 놓치면, 실제로 도달할 수 없는 위치까지 계산하게 됩니다.

 

• 길이가 1인 배열은 시작점이 곧 도착점이므로 항상 True입니다.

유사 문제 패턴

• 최소 점프 횟수 구하기: 도달 가능 여부가 아니라 마지막까지 가는 최소 이동 횟수를 묻는 문제입니다.

 

• 주유소/배터리 문제: 현재 자원으로 갈 수 있는 최대 범위를 갱신한다는 점에서 비슷합니다.

 

• 구간 커버 문제: 여러 구간으로 목표 지점을 덮을 수 있는지 판단하는 greedy 문제와 연결됩니다.