[LeetCode]Jump Game II

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

Jump Game II - LeetCode

 

문제 분석

nums 리스트에는 한번에 점프할 수 있는 최대의 값이 들어 있습니다. 목적지에 도달하기 위해 점프를 가장 적게하는 횟수를 구하는 문제입니다.

 

처음 시도한 답안

class Solution:
    def jump(self, nums: List[int]) -> int:
        count = 0
        # 현재 구간에서 1번의 점프만으로 도달 가능한 가장 먼 위치
        curr_jump_max = 0
        # 현재 구간에서 도달 가능한 가장 먼 위치
        next_jump_max = 0

        for idx in range(len(nums)-1):
            # 각 구간에서 도달 가능한 가장 먼 위치를 추적하고 갱신합니다.
            next_jump_max = max(nums[idx] + idx, next_jump_max)

            # 현재 구간 == 도달 가능한 가장 먼 위치에 도착한 경우, 점프합니다.
            # 즉, 점프를 해야만 하는 경우
            if idx == curr_jump_max:
                # 단, idx 0번째의 경우 바로 카운트가 1회 증가함
                count += 1
                # 현재 구간의 위치를 점프한 곳으로 초기화 합니다.
                curr_jump_max = next_jump_max

        return count

# [2,3,1,1,4]
#  0,1,2,3,4
# next_jump_max
# [2,4,4,4,]
# curr_jump_max
# [2,2,4,]

접근 방법

1. 현재 구간에서 가장 멀리 점프할 수 있는 위치와 도달 가능한 가장 먼 위치를 기록합니다.
   현재 구간이란 count가 1 증가하기 전까지의 구간을 말합니다.
2. 마지막 도달하는 경우는 무시하고 순회합니다.
3. 현재 구간에서 가장 멀리갈 수 있는 위치의 max 값을 찾아서 갱신합니다.
4. idx 가 curr_jump_max와 같다면 점프를 한 것으로 간주하고 카운트를 1회 증가합니다.
5. curr_jum_max를 점프를 한 위치로 변경합니다.
   (이후 반복에서 next_jump_max는 다음 점프까지 멀리 갈 수 있는 위치가 갱신됩니다)

해당 문제를 풀이하기 위한 적절한 방법이 떠오르지 않아 솔루션을 참고 했습니다. 점프해서 도달할 수 있는 최대 거리와 현재 구간에서 멀리갈 수 있는 거리를 이용한 것은 이해가 잘 갔지만, idx가 0인 경우에 카운트를 1회 하고 시작한다는 점이 이해하기에 어려웠습니다.