LeetCode 55 - Jump Game

문제 설명

nums 배열이 주어졌을 때, 처음 인덱스에서 시작하여 마지막 인덱스에 도달할 수 있는지 판단하는 문제입니다. 각 원소 nums[i]는 해당 인덱스에서 최대 몇 칸까지 점프할 수 있는지를 의미합니다.

접근 방법 - Greedy (그리디) 방식

핵심 아이디어

• 매 순간 현재 위치에서 갈 수 있는 최대 거리(maxReach) 를 업데이트합니다.
• 현재 인덱스가 maxReach보다 크다면 더 이상 앞으로 진행할 수 없으므로 false를 반환합니다.
• 끝까지 도달하면 true를 반환합니다.

코드

function canJump(nums: number[]): boolean {
  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
}

시간 및 공간 복잡도

구분	복잡도
시간 복잡도	O(n)
공간 복잡도	O(1)

주요 포인트

• 최적화된 Greedy 접근법
• 매 순간 도달 가능한 최대 거리만 신경 쓰는 단순한 로직
• 조기 종료 조건을 통해 불필요한 연산 최소화