[LeetCode] 55. Jump Game 풀이 (Java)

 

✔️ 오늘의 리트코드 공부 기록 – Jump Game

---

 

문제 요약 (Jump Game)

정수 배열 nums가 주어진다.
각 원소 nums[i]는 현재 인덱스 i에서 최대 몇 칸까지 점프할 수 있는지를 의미한다.

배열의 첫 번째 인덱스(0)에서 시작해서
마지막 인덱스에 도달할 수 있는지를 판단하는 문제다.

• 문제 링크: https://leetcode.com/problems/jump-game

---

 

🤔 처음 떠올린 아이디어

처음 문제를 봤을 때는 이렇게 생각했다.

현재 위치에서 갈 수 있는 모든 경우를 다 탐색해보면 되지 않을까?

그래서 자연스럽게 떠오른 접근은:
재귀,DFS 혹은 DP


즉, 현재 인덱스에서
1 ~ nums[i] 만큼 점프해 보면서
하나라도 끝에 도달하면 true를 반환하는 방식이다.

논리적으로는 맞는 접근이다.
실제로 구현도 어렵지 않다.

---

 

문제를 풀다 보니 이런 의문이 들기 시작했다.

내가 어떤 경로로 여기까지 왔는지가… 정말 중요할까?

 

💡 사고의 전환 포인트

여기서 관점을 바꾸게 됐다.

• 기존 생각: “지금 위치에서 어디로 점프할 수 있지?”
• 바뀐 생각: “지금까지 어디까지 갈 수 있었지?”

이 문제에서 중요한 건

어떤 점프를 했는지(경로)가 아니라
도달 가능한 범위였다.

---

 

💡 핵심 깨달음: 상태는 하나면 충분하다

DP처럼 생각하면 상태는 이런 느낌이다.

dp[i] = i에 도달할 수 있는가?

하지만 Jump Game에서는
이걸 전부 저장할 필요가 없다.

왜냐하면:

어떤 인덱스 i에 도달할 수만 있다면
과거에 어떤 경로로 왔는지는 이후 선택에 영향을 주지 않는다

그래서 상태를 하나로 줄일 수 있다.

• maxReach = 지금까지 도달 가능한 가장 먼 인덱스

---

 

🧠 Greedy 사고 흐름 정리

생각을 순서대로 정리하면 이렇다.

1. 처음에는 0번 인덱스에 있으므로 maxReach = 0
2. 배열을 왼쪽부터 순회한다.
3. 만약 현재 인덱스 i가 maxReach보다 크다면? 그 위치에는 애초에 도달 불가능 -> 바로 false
4. 아니라면, i + nums[i]로 갈 수 있는 최대 범위를 계산하고 maxReach를 갱신한다.
5. 끝까지 막히지 않으면 true

---

📌 이 문제에서 Greedy가 가능한 이유

이 문제는 다음 조건을 만족한다.

• 과거 선택이 미래 선택을 제한하지 않는다
• 경로 정보는 의미가 없고, 범위 정보만 중요하다
• “최대 / 최소” 같은 단어가 핵심 상태로 등장한다.
  
  👉 이런 문제는 Greedy로 상태를 압축할 수 있다.

---

💻 코드 (Java)

class Solution {
    public boolean canJump(int[] nums) {
        int maxReach = 0;

        for (int i = 0; i < nums.length; i++) {
            if (i > maxReach) return false; // 이 인덱스에는 물리적으로 도달할 수 없다
            maxReach = Math.max(maxReach, i + nums[i]); // → 현재 위치를 이용해 도달 범위를 확장한다
        }
        return true;
    }
}

 

📈 시간 / 공간 복잡도

 

• 시간 복잡도: 배열 한 번 순회 → O(N)
• 공간 복잡도: 추가 공간 없음 → O(1)

---

📝 이번 문제에서 얻은 깨달음

• DFS / DP로 시작하는 건 자연스럽다.
• 하지만 “정말 필요한 상태가 뭔지”를 다시 생각해야 한다.
• Jump Game은 경로 문제가 아니라 도달 범위 문제였다.

👉 결국 중요한 건
“그리디를 떠올렸는가”가 아니라
“문제를 어떤 관점으로 다시 봤는가”였다.