[LeetCode] Jump Game (Top Interview Questions Medium)

Problem Link : https://leetcode.com/explore/interview/card/top-interview-questions-medium/111/dynamic-programming/807/

Category : Dynamic Programming

Language : Python 3, Java

---

풀이

이 문제는 시간복잡도 $O(n^2)$으로는 통과할 수 없습니다. 처음 생각한 풀이는 각 칸에 대해서 최대 이동 가능한 수까지 움직여 보고 모든 수를 더해보는 것이었으나 $O(n^2)$으로 시간초과가 나왔습니다.

 

그렇다면 DP에서 흔히 생각해보는 방법인 중복된 경우 가지치기를 해봅니다. 총 4칸이 있고 [3,2,1,0]를 인풋으로 받는다면, 2번 칸(index)에서는 1번 칸에서 넘어온 경우와 0번 칸에서 바로 넘어온 경우 두 가지가 있고, 3번 칸에서는 0, 1, 2번 칸에서 넘어온 세 가지 경우가 있을 것입니다. 뒤 칸에서부터 앞으로 오는 순서로 생각해보겠습니다. (커서 cur를 3 -> 0으로 움직여보겠습니다.)

 

3번 칸에서는 0, 1, 2번에서 넘어온 경우를 모두 생각할 필요가 없습니다. 탐욕 알고리즘(Greedy Algorithm) 쪽으로 접근해보겠습니다. 0, 1번 칸에서 온 경우는 2번 칸에서 다시 생각할 기회가 남았습니다. 왜냐하면 조건은 "최대" n 개 칸을 옮길 수 있다이기 때문입니다. 즉, 0 -> 3 경로로 이동할 수 있다면, 0 -> 1 or 0 -> 2로 움직이는 것도 가능하기에 0 -> 1 -> 2 or 0 -> 2 경로는 다음 번에 2 칸을 방문했을 때 고려할 수 있습니다.

3번 칸에서 욕심을 부려 2번으로 가는 것을 선택했다면, 2번 칸에서는 1 -> 2를 선택할 것입니다.

2번 칸에서 1번을 선택했다면, 1번 칸에서는 0 -> 1를 선택할 것입니다.

 

3번에서 출발한 커서가 무사히 0번까지 왔으므로 (cur == 0) 이 테스트 케이스는 True를 리턴할 것입니다.

 

제출 코드

Python 3 코드

Runtime : 460ms / Memory Usage : 15.3MB

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        cur = len(nums)-1

        for j in range(cur-1, -1, -1):
            if nums[j] >= cur-j:
                cur = j

        return cur == 0

Java 코드

Runtime : 1ms / Memory Usage : 39.4MB

class Solution {
    public boolean canJump(int[] nums) {
        int cur = nums.length - 1;

        for (int j=cur; j>=0; j--) {
            if (nums[j] >= cur-j) {
                cur = j;
            }
        }

        return cur == 0;
    }
}