55. Jump Game

LeetCode 55번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

Jump Game - LeetCode

풀이 1

아이디어

문제를 보자마자 처음으로 떠올렸던 방법. 접근이 가능한 곳에서 그 다음으로 접근 가능한 곳들을 체크해나간다. 마지막 dp 배열의 마지막 원소가 true가 된다면 마지막 지점까지 도달 가능한 것.

직관적이긴 하지만 같은 원소에 반복적으로 접근하는 경우가 많아서 비효율적이다. (같은 지점에 도달할 수 있는 방법이 여러가지이므로…)

코드

function canJump(nums: number[]): boolean {
  const canAccess = Array(nums.length).fill(false);
  canAccess[0] = true; // 시작점은 접근 가능

  for (let idx = 0; idx < nums.length; idx++) {
    if (canAccess[idx]) {
      // 현재 위치에서 다음에 도달 가능한 지점들 표시하기
      for (let jump = 1; jump <= nums[idx]; jump++) {
        const next = idx + jump;
        if (next >= nums.length - 1) return true;
        if (!canAccess[next]) canAccess[next] = true;
      }
    }
  }

  return canAccess[nums.length - 1];
}

풀이 2

아이디어

우리가 구해야 하는 것은 경로가 아니라 “도달 가능한가?”이기 때문에 DP처럼 모든 과정을 기록할 필요는 없다. 따라서 현재 위치에서 도달 가능한 최대 지점을 계속 업데이트해나가는 Greedy 방식으로 풀면 시간복잡도 O(n) 으로 효율적으로 풀 수 있다.

코드

function canJump(nums: number[]): boolean {
  let maximumPos = 0;

  for (let curr = 0; curr <= maximumPos; curr++) {
    const reachable = curr + nums[curr];
    if (reachable >= nums.length - 1) return true;
    maximumPos = Math.max(reachable, maximumPos);
  }

  return false;
}