일차원 배열 Jump 문제 연습 - Greedy 알고리즘

                                    ⚠️ n = 1..10000

🤔 DFS? Greedy?
>>> map을 사용하면 간단하게 풀 수 있을 것 같은데?

✅ i -> 0 .. n-1까지 이동하면서 map을 업데이트한다.
✅ map = {i: minimum jump count}로 기록한다.
>>> 초기 값은 9999999로 set 하자.
>>> 🗝️ 매 순간 nums[i]에서 자신까지의 최솟값을 확인한다
>>> ➡️ 자신이 도달할 수 있는 값을 모두 확인 후 가능한 해당 위치의 최솟값을 갱신한다.
✅ O(n)의 시간 복잡도로 마지막 위치까지 점프 횟수를 계산할 수 있다.

                                    class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        jump = {}
        n = len(nums)

        for i in range(n):
            jump[i] = 9999999

        jump[0] = 0

        for i, num in enumerate(nums):
            step = num
            for j in range(1, step + 1):
                if i + j >= n:
                    break

                jump[i + j] = min(jump[i + j], jump[i] + 1)

        print(jump)
        return jump[n - 1]

                                    ✅ 각 구간에서 가능한 최대거리를 추적한다.
✅ 이와 동시에 현재 위치를 추적하며, 만약 현재 위치가 최대 거리 범위에서 벗어나지 못햇다면 step을
증가시키지 않으면 된다.

                                    class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n == 1:
            return 0

        maxReachable = 0
        coverage= 0
        jump = 0

        for i, num in enumerate(nums):
            # update new maxReachable
            maxReachable = max(maxReachable, i + num)
            if i == coverage:
                jump += 1
                coverage = maxReachable

                if coverage >= n - 1:
                    return jump

                                    [2, 3, 1, 1, 4]
[       ] = coverage
     [        ]  = max Reachable

i가 coverage를 벗어나는 순간 최대 Reachable로 이동한다.
>>> 이때 coverage의 위치가 현재 위치이며 만약 >= n -1인 경우 끝이다.