[Medium] 점프 게임 II - 45. Jump Game II

당신은 길이 n의 정수 배열 nums를 입력으로 받습니다. 당신은 처음에 nums[0] 위치에 있습니다.

각 요소 nums[i]는 인덱스 i에서 앞으로 점프할 수 있는 최대 거리를 나타냅니다. 즉, 만약 당신이 nums[i]에 있다면, nums[i + j]로 점프할 수 있습니다. 여기서:

• 0 <= j <= nums[i] 이고
• i + j < n

nums[n - 1]에 도달하기 위한 최소 점프 횟수를 반환하세요. 테스트 케이스는 nums[n - 1]에 도달할 수 있도록 생성됩니다.

예시 1:

입력: nums = [2,3,1,1,4]
출력: 2
설명: 마지막 인덱스에 도달하기 위한 최소 점프 횟수는 2입니다. 인덱스 0에서 1로 1칸 점프하고, 그 다음 3칸을 점프하여 마지막 인덱스로 이동합니다.

예시 2:

입력: nums = [2,3,0,1,4]
출력: 2

제한 사항:

• 1 <= nums.length <= 10⁴
• 0 <= nums[i] <= 1000

nums[n - 1]에 도달할 수 있는 것이 보장됩니다.

 

풀이

class Solution:

    def jump(self, nums: List[int]) -> int:
        n = len(nums)  # 배열의 길이를 변수 n에 저장
        if n == 1:  # 배열의 길이가 1이라면 점프할 필요가 없으므로 0을 반환
            return 0

        jumps = 0  # 점프 횟수를 저장하는 변수
        current_end = 0  # 현재 점프에서 도달할 수 있는 마지막 인덱스
        farthest = 0  # 현재까지 점프한 위치에서 도달할 수 있는 가장 먼 인덱스

        for i in range(n - 1):  # 마지막 인덱스를 제외한 인덱스들에 대해 반복
            farthest = max(farthest, i + nums[i])  # 현재 인덱스에서 갈 수 있는 가장 먼 위치 계산

            if i == current_end:  # 현재 인덱스가 점프의 끝인 경우
                jumps += 1  # 점프 횟수 증가
                current_end = farthest  # 다음 점프의 끝을 업데이트

                if current_end >= n - 1:  # 만약 다음 점프의 끝이 배열의 끝을 넘는다면 반복을 종료
                    break

        return jumps  # 최소 점프 횟수를 반환