[리트코드] 55. Jump Game

문제

https://leetcode.com/problems/jump-game/

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

---

✔ 문제접근 #1 bfs[시간초과]❌

Intuition
현재 인덱스를 기준으로하여 bfs탐색을하며 마지막 지점에 도착할 수 있는지 판단한다.

Algorithm
시작점 x = 0을 기준으로 bfs 탐색한다. 다음값의 범위는 nums[i]의 값이 5라고 했을 때 index [-5, 5]까지의 값들을 q에 넣어서 탐색해준다. 이때 배열 nums의 길이범위를 넘어가는 값은 continue처리를 통해 무시한다.

    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        
        # 시작 index와 마지막 index가 같다면 무조건 true
        if n == 1:
            return True
        
        
        # bfs를 통해서 마지막 인덱스에 도착할 수 있는지 확인한다.
        q = deque()
        visited = [False] * (n + 100000)
        visited[0] = True
        q.append(0)
        ans = False
        
        while q:
            x = q.popleft()
            
            # index가 0보다 작다면 무시
            if x < 0:
                continue
            
            # index가 n - 1보다 크다면 도착할 수 있다고 간주하고 True 리턴
            if x >= n - 1:
                ans = True
                break
                
            dist = nums[x]
            for dx in range(-dist, dist + 1):
                nx = x + dx
                
                if not visited[nx]:
                    q.append(nx)
                    visited[nx] = True     
        
        return ans

실행결과

Complexity Analysis

• 시간 복잡도 : O(N*K)
  • 배열의 전체길이를 BFS로 탐색 O(N)
  • 배열요소의 값의 길이만큼 탐색하는 양 추가 O(K)
  • 그러므로 전체시작복잡도 : O(N*K)

• 공간복잡도 : O(N)
  
  • deque자료구조 및 방문처리를 위한 visited 배열 사용

---

✔ 문제접근 #2 선형탐색[통과] ⭕

Intuition
현재 위치로부터 최대로 갈 수 있는 위치를 계속해서 갱신해나간다.

Algorithm
max_idx라는 변수로 갈 수 있는 최대치를 갱신해나간다.

배열을 순회하며 만약 현재 배열의 인덱스가 max_idx보다 작다면 갈 수 있는 위치이기 때문에 해당 위치에서 마지막 지점까지 갈 수 있는지 확인한다.

그리고 해당 위치에서 갈 수 있는 최대치를 갱신해준다.

    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        max_idx = 0 # 최대로 이동가능한 거리
        
        for i in range(n):
            if i > max_idx:
                continue
            
            if i <= max_idx and i + nums[i] >= n - 1:
                return True
            
            max_idx = max(max_idx, i + nums[i])
            
        return False

실행결과

Complexity Analysis

• 시간 복잡도 : O(N)
  • nums 배열을 순차탐색 O(N)
  • 그러므로 전체시작복잡도 : O(N)

• 공간복잡도 : O(1)
  
  • 추가 배열 사용 x

---

기타풀이 및 회고

처음에는 도달 할 수 있는지에 초점을 맞춰서 생각했기 때문에 bfs방식을 생각했었다. 하지만 해당값의 범위만큼 모두 탐색하려면 시간이 너무 오래걸렸고 단순히 순차탐색으로도 갈 수 있는 최대범위를 기록해가며 해결할 수 있었다. 문제의 유형에 익숙한 나머지 쉽게 해결할 수 있었던 문제를 너무 어렵게 생각했던 것 같다.