[LeetCode 55] Jump Game - 탐욕법(Greedy) 풀이 및 최적화

[LeetCode] Jump Game - 탐욕법(Greedy) 풀이 및 최적화

문제 설명

LeetCode의 "Jump Game" 문제는 배열의 시작점에서 끝점까지 도달할 수 있는지 확인하는 문제입니다.

• nums[i]는 i번째 인덱스에서 최대 몇 칸까지 점프할 수 있는지를 나타냅니다.
• nums[0]에서 nums[n-1]까지 도달할 수 있으면 true, 불가능하면 false를 반환해야 합니다.

---

📌 처음 문제를 풀었을 때의 접근 방식

처음에는 배열을 사용하여 방문 가능 여부를 체크하는 방식으로 접근했습니다.

export function canJump(nums: number[]): boolean {
  const list = new Array(nums.length).fill(false); // 방문 가능 여부 배열
  list[0] = true; // 첫 번째 위치에서 시작 가능

  for (let i = 0; i < nums.length; i++) {
    if (!list[i]) continue; // 현재 위치(i)가 도달 가능하지 않다면 스킵
    let index = i;
    while (index < nums.length && index <= i + nums[i]) {
      list[index++] = true; // 현재 위치에서 갈 수 있는 범위까지 도달 가능 표시
    }
  }

  return list[nums.length - 1]; // 마지막 인덱스 도달 가능 여부 반환
}

✅ 동작은 하지만, 비효율적! (O(N^2) 시간복잡도로 최적화 필요)
✅ 공간 복잡도도 O(N), 추가 배열 사용으로 메모리 낭비

---

📌 최적화된 접근법: 탐욕법(Greedy Algorithm)

이 문제는 **탐욕법(Greedy Algorithm)**을 사용하면 효율적으로 O(N) 시간복잡도로 해결 가능합니다.

✅ 탐욕법(Greedy) 핵심 아이디어

• **"최대로 도달할 수 있는 위치(maxReach)"**를 계속 갱신하면서, n-1번째 인덱스까지 도달할 수 있는지 확인합니다.
• 현재 인덱스(i)가 maxReach보다 크면 → 더 이상 진행할 수 없으므로 false 반환.

export function canJump(nums: number[]): boolean {
  let maxReach = 0; // 최대로 도달할 수 있는 위치

  for (let i = 0; i < nums.length; i++) {
    if (i > maxReach) return false; // 현재 위치(i)가 maxReach보다 크면 도달 불가능
    maxReach = Math.max(maxReach, i + nums[i]); // 최대 이동 가능한 위치 갱신
    if (maxReach >= nums.length - 1) return true; // 마지막 인덱스에 도달 가능하면 바로 true 반환
  }

  return false;
}

✅ 시간복잡도: O(N), 배열을 한 번만 순회
✅ 공간복잡도: O(1), 추가 배열 없이 해결 가능

---

📌 실행 예제 분석

nums = [2,3,1,1,4]

i nums[i] maxReach 설명

0	2	2	0 + 2 = 2 (0번 인덱스에서 최대 2칸 이동 가능)
1	3	4	max(2, 1 + 3) = 4 (1번 인덱스에서 4번까지 이동 가능)
2	1	4	max(4, 2 + 1) = 4 (2번 인덱스에서 3번까지만 이동 가능)
3	1	4	max(4, 3 + 1) = 4 (3번 인덱스에서 4번까지 이동 가능)
4	4	8	max(4, 4 + 4) = 8 (마지막 인덱스 도달 가능)

✅ 결과: true

---

📌 시간 및 공간 복잡도 비교

방법 시간 복잡도 공간 복잡도 특징

배열 활용 (초기 풀이)	O(N^2)	O(N)	비효율적, 추가 배열 필요
탐욕법 (Greedy)	O(N)	O(1)	최적의 방법, 빠름

✅ 탐욕법(Greedy)이 최적의 해결법!

---

📌 Jest 테스트 코드

describe("Jump Game", () => {
  it("returns true for reachable last index", () => {
    expect(canJump([2,3,1,1,4])).toEqual(true);
  });

  it("returns false for unreachable last index", () => {
    expect(canJump([3,2,1,0,4])).toEqual(false);
  });

  it("returns true for single element array", () => {
    expect(canJump([0])).toEqual(true);
  });

  it("returns true when all elements are large", () => {
    expect(canJump([10,10,10,10,10])).toEqual(true);
  });

  it("returns false for early stopping case", () => {
    expect(canJump([1,0,0,0])).toEqual(false);
  });
});

✅ 다양한 입력 케이스 검증하여 정확성 확보
✅ 테스트 케이스 추가 (단일 요소, 큰 값, 초기 정지 상황)

---

📌 최종 정리

• 탐욕법(Greedy)이 최적의 해결법 (O(N))
• "최대 도달 가능 위치(maxReach)"를 계속 갱신하면서 도달 여부 판단
• 추가 배열을 사용하지 않고 O(1) 공간복잡도로 해결 가능
• 테스트 케이스를 추가하여 다양한 상황에서 올바른 결과 확인 가능

💡 이제 비슷한 문제를 만나면 "탐욕법"을 우선 고려해 보세요! 🚀