릿코드 45. Jump Game II

이 글은 Tistory에서 이전된 포스팅입니다. 원본은 여기에서 확인할 수 있습니다.

문제 링크

https://leetcode.com/problems/jump-game-ii/description/?envType=study-plan-v2&envId=top-interview-150

접근

$ \bullet $ 마지막 인덱스에 도달할 수 없는 case는 없다.

$ \bullet $ 그래서, (마지막 인덱스 제외하고) 특정 인덱스에 도달할 수 있는지는 상관없다.

$ \bullet $ 범위로 생각해보자. STEP당 도달할 수 있는 최대 인덱스, 다음 인덱스부터는 STEP+1의 범위이다.

$ \bullet $ 마지막 인덱스는 몇 번째 STEP 범위에 속할지 알아보자.

처음에 특정 인덱스까지 도달하는데 최소 step을 dp에 update하면서 풀고 통과 했는데 속도가 너무 느렸다.

다른 코드를 보고 범위로 접근해야하는 문제인 걸을 알았다. 아래는 수정한 코드이다.

class Solution:
    def jump(self, nums: List[int]) -> int:
        max_idx = 0
        end_of_jump = 0
        jump = 0
        for i in range(len(nums)-1):
            max_idx = max(max_idx, i+nums[i])
            if i == end_of_jump:
                jump += 1
                end_of_jump = max_idx
        return jump

반복문이 시작하면서 end_of_jump = $ A[0] $ 가 된다.

그러면 jump=1 범위에서는 조건문에 안걸리고 max_idx만 업데이트한다.

그러다 jump=1 범위 마지막에 조건문에 걸리고 jump=1에서 제일 멀리 갈 수 있었던 index를 end_of_jump에 업데이트한다.

jump=2 범위에서 위의 과정을 반복한다.

$ … $

$ A_{0} … A_{n-2} $ 까지 순회하면 jump는 마지막 범위에 해당하는 값으로 업데이트돼있을 것이다.

$ A_{n-1} $ 까지 안보는 이유는, 범위 마지막에 최종 인덱스가 있다면 다음 로직을 위해 jump += 1 을 하기 때문에 $ A_{n-2} $ 까지 반복한다.

수정 전 코드

class Solution:
    def get_min_count(self, nums, target_idx, dp):
        # print(dp, target_idx)
        if target_idx == 0:
            return 0
        result = []
        for i in range(target_idx-1, -1, -1):
            if nums[i] >= target_idx - i:
                if dp[i] == "x":
                    dp[i] = self.get_min_count(nums, i, dp)
                
                if dp[i] == -1:
                    continue
                else:
                    result.append(dp[i])
        # print("out",dp, target_idx, result)
        return min(result) + 1 if len(result) > 0 else -1

    def jump(self, nums: List[int]) -> int:
        dp = [ "x" for _ in range(len(nums)) ]
        return self.get_min_count(nums, len(nums)-1, dp)