[DSA][Greedy] 02. Jump Game

LeetCode 55

 

02. Jump Game

You are given an integer array nums.
You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

 

 

[질문하기]

- 배열에 음수가 포함될 수 있나요? NO

 

[아이디어]

- (forward) 현재 위치에서 도달 가능한 최대 인덱스를 계속 갱신하며, 각 위치가 도달 가능한지 확인한다.

- (backward) 뒤에서부터 탐색하며, 각 위치에서 목표 지점에 도달 가능한지 판단하고 목표 지점을 앞쪽으로 이동시킨다.

 

 

[풀이 1] Greedy (Forward)

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        max_reach = 0
        for i in range(len(nums)):
            if i > max_reach:
                return False
            max_reach = max(max_reach, i + nums[i])
        return True

이 코드는 nums 배열을 왼쪽에서 오른쪽으로 한 번 순회하면서, 현재 위치까지 도달 가능한지를 판단하고, 동시에 가장 멀리 도달 가능한 위치(max_reach)를 업데이트하는 그리디 알고리즘이다.

 

max_reach는 지금까지 내가 도달할 수 있었던 가장 먼 인덱스를 나타낸다. 처음 시작점은 무조건 도달 가능하기 때문에 max_reach를 0으로 초기화한다.

 

매번 인덱스 i를 순회하면서, 만약 i가 max_reach보다 크다면, 내가 도달할 수 있는 최대 거리보다 현재 위치가 앞서 있다는 의미이므로 False를 return 한다. 도달 가능한 위치라면, max_reach를 현재 값 + 현재 위치 (nums[i] + i)를 통해 현재 위치에서 가장 멀리 갈 수 있는 값으로 업데이트한다.

 

 

[풀이 2] Greedy (Backward)

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        goal = len(nums) - 1
        
        for i in range(len(nums) - 2, -1, -1):
            if i + nums[i] >= goal:
                goal = i
        return goal == 0

이 코드는 위와는 반대로 뒤에서부터 거꾸로 탐색하면서, i + nums[i]가 goal보다 크거나 같으면 현재 위치에서 goal에 도달할 수 있다는 의미이기 때문에 goal을 i로 갱신한다.

비록 현재 위치에서는 goal에 도달하지 못하더라도, 그보다 앞선 위치에서 goal에 도달할 수 있다면 결국 마지막까지 도달 가능하기 때문에 거꾸로 탐색하다가 마지막에 goal이 0이 되는지를 확인하면 된다.

 

 

⏱️ 시간복잡도

배열을 한 번만 순회하므로 시간 복잡도는 O(n)이다.

🧠 공간복잡도

추가적인 공간을 거의 사용하지 않기 때문에 공간 복잡도는 O(1)이다.