45. Jump Game II

LeetCode Medium 45. Jump Game II Python

💡 문제

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

45. Jump Game II

🥳 해결!

생각

1. 해당 값 안에 있는 가장 큰 숫자를 찾아, 갈 수 있는 거리 측정
2. 갈 수 있는 거리를 미리 for문으로 측정하여 리스트 저장

처음엔 전자로 풀려다가
갈 수 있는 거리를 그때 그때 측정하는 일은 아니라는 판단이 들었다.

그래서 두번째 방법으로 접근했다.

  class Solution(object):
    def jump(self, nums):
        # 각 위치에서 갈 수 있는 최대의 길이
        maxList = [nums[i] + i for i in range(len(nums))]
        startIdx = 0
        move = 0 # 가장 멀리 갈 수 있는 위치
        cnt = 0

        while move < len(nums)-1: # idx 이기 때문에 -1
            cnt += 1
            # 다음 탐색 시작 위치는 인덱스 기준이므로 move+1
            startIdx, move = move+1, max(maxList[startIdx:move+1])

        return cnt
      

처음엔 초기 값으로 초기화 하고 시작하려 했으나,
nums 가 [0]으로 주어지는 테스트 케이스가 있었다.

그래서 위와 같이 해결!