[알고리즘/Python] LeetCode 55. Jump Game

문제

https://leetcode.com/problems/jump-game/?envType=study-plan-v2&envId=top-interview-150

Jump Game - LeetCode

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.
 
Example 1:
Input: nums = [2,3,1,1,4] Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:
Input: nums = [3,2,1,0,4] Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
 
Constraints:
1 <= nums.length <= 10^4
0 <= nums[i] <= 10^5

---

접근방법: Dynamic Programming

이문제는 각 칸에서 점프해서 마지막 칸에 도달할 수 있는지 체크하는 문제이다. DP[i]를 i번째칸에서 최대로 점프할 수 있는 칸 수라고 할때 DP[i] = max(DP[i-1] - 1, nums[i])로 구할 수 있다. 즉, 이전 칸에서 최대로 점프하거나, 현재 칸에서 최대로 점프하는 경우 중 큰 값이 현재 칸에서 최대로 점프할 수 있는 칸 수가 된다. 이때 새로운 배열을 할당하기 보다, 기존 배열의 값을 최대값으로 갱신할 수 있다.

 

1. 만약 첫번째 칸에서 전혀 뛸 수 없는 경우 마지막칸에 도달할 수 없으므로 False를 반환하고, 첫번째 칸이 마지막칸인 경우 뛰지 않아도 되므로 True를 반환한다.

2. 두번째 칸부터 마지막 이전 칸까지 순회하면서 각 칸의 값을 현재 칸에서 최대로 뛸 수 있는 값으로 갱신한다. 현재 칸에서 최대로 뛸 수 있는 값은 (이전 칸에서 최대로 뛸 수 있는 칸 - 1) 혹은 (현재 칸에서 최대로 뛸 수 있는 칸) 중에 큰 값이 된다. 마지막 칸에 도달하는 것이 목표이므로 마지막 칸에서는 더 나아갈 수 없어도 상관이 없다.

3. 만약 현재 칸에서 뛸 수 있는 최대 칸이 0인 경우 더 이상 진행할 수 없으므로 False를 반환한다.

4. 마지막 이전 칸까지 순회가 끝났다면 마지막 칸에 도달할 수 있기 때문에 True를 반환한다.

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

주의할 점은 nums의 길이가 1인 경우는 뛰지 않아도 마지막 인덱스에 도달한 것이기때문에 항상 True를 반환해야하며, nums = [0, 1]처럼 첫번째 칸의 값이 0인 경우는 항상 False를 반환해야 한다는 것이다.

✔️ 시간 복잡도 및 공간 복잡도

시간 복잡도: O(N). nums 배열을 한번 순회하므로 배열의 길이 N에 비례하는 선형 시간이 걸린다.

공간 복잡도: O(1). 새로운 배열을 할당하지 않고 기존 배열의 값을 갱신하는 방식으로 진행하기 때문에 추가 공간이 필요 없다.

---

🤔 다른 사람의 풀이: 뒤에서부터 거꾸로 체크

 뒤에서부터 확인해가는 방식도 있다. 뒤에서부터 거꾸로 체크하면서 현재 칸에 도달할 수 있는 방법이 있는지 확인하고, 현재 칸에 도달할 수 있는 칸이 있다면, 다시 그 칸에 도달할 수 있는 방식이 있는지 체크한다.

 

  1. 도달하고자 하는 목표지점을 나타내는 변수 goal을 배열의 마지막 index로 초기화한다.

  2. 마지막 이전 칸에서부터 거꾸로 순회하면서 현재 칸에서 goal까지 도달할 수 있는지 체크한다. goal에 도달할 수 있다면 다음 도달해야하는 goal은 현재 칸이 된다.

  3. 전체 배열을 순회하고나서 goal이 0보다 크다면 첫번째 칸에서 goal에 도달할 수 있는 방법이 없다는 의미로 마지막 칸에 도달할 수 없으므로 False를 반환하고, goal 이 0이라면 True를 반환한다.

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 True if goal == 0 else False #return goal == 0

 이 방식은 시간 복잡도 O(N), 공간 복잡도 O(1)로 실제 실행시간도 위의 방식과 비슷하게 걸린다. 위의 방식과 달리, 배열의 길이가 1이거나 출발지점에서 점프할 수 없는 경우 등 edge case를 따로 체크하지 않아도 된다는 장점이 있다. 

---

✅ 정리

◎ 배열을 활용한 알고리즘 문제를 풀때는 앞에서부터 혹은 뒤에서부터 자유자재로 생각할 수 있어야하며, 문제 상황에 맞는 적절하고 효율적인 방식을 선택할 수 있어야한다.