[Leetcode] 45. Jump Game II

문제

https://leetcode.com/problems/jump-game-ii/description/?envType=study-plan-v2&envId=top-100-liked

풀이

DP를 이용해서 처음에 제출한 풀이는 다음과 같다. 시간복잡도는 O(N^2)으로 AC를 받을 수는 있었다. 그러나 시간효율이 너무 안좋게 나와서 discussion을 보니 O(N)의 풀이가 가능한 것으로 보여서 고민했다.

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        min_jumps=[float('inf')] * n # 해당 위치 도달할때까지 최소 점프수 저장할 자료구조
        min_jumps[0] = 0

        for i,num in enumerate(nums):
            if min_jumps[i] != float('inf'): # 도달 가능한 위치일 때
                for j in range(num+1):
                    if i+j >= n: # 범위 초과하면 break
                        break
                    min_jumps[i+j] = min(min_jumps[i+j], min_jumps[i]+1)
        
        return min_jumps[-1]

고민하고 BFS를 이용하는 풀이로 바꿨으나 해당 풀이도 결국 시간복잡도는 O(N^2)이 되었다. (방문 여부를 체크하더라도 모든 원소마다 리스트 끝까지 for문을 돌게되므로)

from collections import deque

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        
        queue = deque([[0,0]]) # [idx, cnt]
        visited = [False]*n
        visited[0] = True

        while queue:
            idx, cnt = queue.pop()
            if idx == n-1:
                return cnt
            
            for j in range(nums[idx]+1): # 0 ~ nums[idx]
                if idx+j >=n:
                    break
                if not visited[idx+j]:
                    queue.appendleft([idx+j, cnt+1])
                    visited[idx+j] = True

O(N)으로 풀기 위해서는 Greedy BFS를 수행했어야 한다. 해당 풀이를 처음에 떠올리기는 매우 힘들어보이고, 풀이를 이해하는데도 시간이 오래 걸렸다.

n번 점프로 도달가능한 곳들을 같은 level로 생각한 그래프를 생각해야 한다.

(출처: https://leetcode.com/problems/jump-game-ii/solutions/1192401/easy-solutions-w-explanation-optimizations-from-brute-force-to-dp-to-greedy-bfs/?envType=study-plan-v2&envId=top-100-liked)

from collections import deque

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)

        ans = 0
        end_idx = 0
        farthest_idx = 0

        # Implicit BFS (Greedy BFS)
        for idx in range(n-1): # 0 ~ n-2 (n-1인덱스는 체크 안해도 됨)
            farthest_idx = max(farthest_idx, idx+nums[idx]) # 최대로 갈 수 있는 인덱스 위치
            if farthest_idx >= n-1: # 마지막 인덱스 도달 가능
                ans += 1
                break
            
            if idx == end_idx: # visited all the items on the current level
                ans += 1 # Increment the level
                end_idx = farthest_idx # Make the queue size for the next level
        
        return ans

• 참고로 처음에 제출한 DP를 이용한 풀이는 내가 푼 방법인 Iterative Dynamic Programming - Tabulation 뿐 아니라 Recursive Dynamic Programming - Memoization 를 통해서도 가능하다.