[Python] Leetcode 45. Jump Game II (Medium)

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

Jump Game II - LeetCode

점프게임의 시리즈 문제입니다.

1번 문제와 달리 도달할 수 있는지의 가부가 아니라 도달하는 최소의 step을 리턴해야 합니다. (마지막 위치에 도달하는것은 문제에서 보장함.)

처음에는 각 index별로 도달하는 최소의 step을 갱신하는 기본적인 DP의 풀이방법으로 풀었는데, 채점에 통과는 되었지만 실행시간이 좋지 않았습니다.

제공되는 testcase의 내용을 확인해 보니 각 index에서 매 번 목적지에 도달이 가능하다면 1차 제출한 코드는 N^2의 시간복잡도를 갖게 된다는 사실을 알게되었습니다.

(예를 들어 100 길이의 배열에 들어있는 숫자가 99,98,97,96...0 이라면 제 코드는 index를 한 칸 진행할 때마다 뒤의 모든 배열을 순회해야 합니다.)

 

처음 제출했던 비효율적인 코드

class Solution:
    def jump(self, nums: list) -> int:
        dp = [20000]*len(nums)
        dp[0] = 0
        
        for i in range(0, len(nums)-1):
            for j in range(i+1, min(len(nums), i + nums[i] + 1)):
                dp[j] = min(dp[i]+1, dp[j])
        return dp[-1]
    

input = [[2,3,1,1,4],[2,3,0,1,4]]

for i in input:
    print(Solution().jump(i))

 

토론 창의 도움을 얻어 BFS와 유사한, 매 step마다 내가 갈수있는 최대의 범위를 갱신하는 코드를 작성했습니다.

class Solution:
    def jump(self, nums: list) -> int:
        step = 0
        position = 0
        canMove = 0
        
        while(position < len(nums)-1):
            step += 1
            maxMove = 0
            
            while(position <= canMove):
                maxMove = max(maxMove, position+nums[position])
                position += 1
                if(maxMove >= len(nums)-1):
                    return step
                
            canMove = maxMove
        
        return step

input = [[0],[2,3,1,1,4],[2,3,0,1,4]]

for i in input:
    print(Solution().jump(i))

 

확실히 실행시간이 어마어마하게 차이가 나네요.