55. Jump Game ★★★

55. Jump Game

 

https://youtu.be/Yan0cv2cLy8?si=bUQX7npOheNXftIY

 

✅ 풀이

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # 목표 위치는 초기에는 마지막 인덱스
        goal = len(nums) - 1

        # 뒤에서부터 순회하며 목표 위치를 갱신
        for i in range(len(nums) - 1, -1, -1):
            # 현재 위치에서 goal에 도달 가능하면 goal을 갱신
            if i + nums[i] >= goal:
                goal = i
        
        # goal이 0이면 시작점에서 도달 가능
        return goal == 0

 

Greedy를 뒤에서부터 적용한 풀이이며, 시간복잡도와 공간복잡도 모두 최적입니다.

---

✅ 로직 설명

goal = len(nums) - 1  # 도달해야 하는 목표 위치는 처음에는 맨 끝

• 리스트를 끝에서부터 순회하면서,
  현재 위치 i에서 goal에 도달할 수 있는 경우,
  즉 i + nums[i] >= goal이면,
  goal을 i로 옮깁니다.

즉, "현재 위치에서 목표에 도달할 수 있다면, 이제 목표는 여기로!" 라고 계속 당겨오는 것입니다.

---

✅ 종료 조건

• 마지막까지 거꾸로 검사해서 goal == 0이 되면 →
  시작점에서 도달 가능한 것이므로 True 반환
• 그렇지 않으면 False

---

✅ 시간/공간 복잡도

• 시간복잡도: O(n)
  전체 배열을 한 번 순회
• 공간복잡도: O(1)
  추가 공간 없이 goal 변수만 사용

---

이 문제는 Greedy (탐욕법) 으로 풀 수 있는 대표적인 문제입니다.

---

✅ 문제 요약

• nums[i]는 현재 위치 i에서 최대 몇 칸까지 점프할 수 있는지를 나타냅니다.
• 시작점은 0이고, 목표는 마지막 인덱스에 도달 가능한지 여부입니다.
• 경로를 구하는 게 아니라 도달 가능성만 판단합니다.

---

✅ 핵심 아이디어 (Greedy)

• max_reach 변수를 이용해, 현재까지 도달 가능한 최대 인덱스를 저장합니다.
• 매 인덱스마다 max_reach를 업데이트 하면서,
  • i > max_reach인 순간이 오면 더 이상 진행할 수 없으므로 False 반환
  • 끝까지 도달하면 True 반환

✅ 파이썬 코드 (O(n))

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        max_reach = 0  # 현재까지 도달 가능한 최대 인덱스

        for i, jump in enumerate(nums):
            if i > max_reach:
                # 현재 위치가 도달 가능한 범위를 벗어남
                return False
            max_reach = max(max_reach, i + jump)
        
        return True

---

✅ 예제 설명

예제 1: nums = [2,3,1,1,4]

• i=0, jump=2 → max_reach=2
• i=1, jump=3 → max_reach=4
• i=2, jump=1 → max_reach=4 (유지)
• 마지막 인덱스(4)에 도달 가능 → True

예제 2: nums = [3,2,1,0,4]

• i=3에서 jump=0 → max_reach=3
• i=4에 도달 못함 → False

---

🧠 시간/공간 복잡도

• 시간 복잡도: O(n)
• 공간 복잡도: O(1)