[Leetcode] 45. Jump Game II

문제 바로가기

DP

nums 리스트의 모든 원소를 순회하면서 해당 원소에 도달하기 위한 최소 jump 수를 기록하는 jumpNums 리스트를 업데이트한다.

Time Complexity: O(n^2)
Space Complexity: O(n)

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        jumpNums = [0] + [float('inf') for i in range(n - 1)]
        
        for i, num in enumerate(nums[:-1]):
            for movable in range(i + 1, i + 1 + num):
                if movable >= n:
                    break
                jumpNums[movable] = min(jumpNums[movable], jumpNums[i] + 1)
        
        return jumpNums[-1]

Greedy

nums 리스트의 모든 원소를 순회하면서 인덱스 i가 현재 점프해있는 인덱스 cur에 도달할때까지 가장 멀리 갈 수 있는 인덱스 far을 구한다. 탐색 인덱스i가 현재 인덱스 cur에 도달한다면 cur를 far로 업데이트해준다.

cur은 실제로 최단 점프 경로라기보다는, 이전 cur과 업데이트된 cur사이의 인덱스 중 하나로 점프를 한다는 것을 의미한다.

Time Complexity: O(n)
Space Complexity: O(1)

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        count = 0
        far = 0  # farthest index
        cur = 0  # current index
        
        for i in range(n - 1):
            far = max(far, i + nums[i])
            if i == cur:
                count += 1
                cur = far

        return count