55 - Jump Game

info

• 문제 보기: 55 - Jump Game
• 소요 시간: 24분 14초
• 풀이 언어: java
• 체감 난이도: 2️⃣~3️⃣
• 리뷰 횟수: ✅

풀이 키워드

스포주의

DP 그리디

풀이 코드

info

• 메모리: 45850 KB
• 시간: 2 ms

class Solution {
    public boolean canJump(int[] nums) {
        int mxIdx = 0; // available max index
        int tdx = nums.length-1; // last index
        for (int i = 0; i < nums.length; ++i) {
            if (i > mxIdx) return false;
            mxIdx = Math.max(mxIdx, i+nums[i]);
            if (tdx <= mxIdx) return true;
        }
        return false;
    }
}

풀이 해설

문제를 처음 보았을 때 dfs 완탐을 떠올렸고 재귀 깊이가 최대 $10^4$ 니까 괜찮지 않나 싶었다.
근데 이 풀이를 쓰며 계산해보니까 시간복잡도가 $O(n!)$ 이어서 택도 없더라.

그리디가 정배지만 DP로도 풀리는 착한(?) 문제이다.

시간복잡도는 nums 배열 한번 스캔하는거라 $O(n)$ 이다.

이 문제가 결국 그리디로 접근 가능한 이유는, nums[i]가 점프 가능한 '최대값이라서' 라고 생각한다.

(해당 값으로만 점프해야된다고 조건이 바뀌면 DP로 풀어야 할 듯)

다시말해 i + nums[i] 이하의 범위들은 다 점프로 올 수 있는 곳들이라는 뜻인데

이를 '접근 가능 영역`으로 정의하면, 또다시 '접근 가능 영역' 내의 최대 점프 값으로 점점 영역을 확장할 수 있고

결국 마지막 인덱스까지 영역 확장이 가능하냐- 의 문제로 치환해볼 수 있다.

---

즉, 풀이 로직의 i > mxIdx는 해당 조건이 true일 시

mxIdx 내의 값들 다 스캔해서 영역 확장해봤는데
i에 도달 못한다는 소리라서,

영역의 한계가 mxIdx로 확정되니 false를 리턴하는 것이다.

---

caution

단순 DFS는 왜 TLE일까?

재귀 트리에서 자식 노드가 많다면 의심을 좀 해보자.

다음의 dfs 코드는 TLE를 받는다.

class Solution {
    int[] gNums;
    boolean ans;

    public void dfs(int i) throws Exception {
        // base case
        if (i == gNums.length-1) {
            ans = true;
            throw new Exception();
        }

        int mx = gNums[i];
        for (int p = 1; p < mx+1; ++p)
            if (i+p < gNums.length)
                dfs(i+p);

        return;
    }

    public boolean canJump(int[] nums) {
        gNums = nums;
        ans = false;
        try {
            dfs(0);
        } catch (Exception e) {
            //
        }

        return ans;
    }
}

빠꾸먹은 tc를 보니 [9997, 9997, 9996, 9995, 9994, ... , 3, 2, 1, 0, 0] 이런식이었다.

즉 nums.length가 $10^4$ 일때 최대의 비효율성을 내도록 한끝 차로 도달 못하게 만든 tc라서

이전의 dfs 풀이는 도달하는 경우를 발견하자마자 끝내버려도 '발견이 안되고 있으니' 최악의 퍼포먼스를 내는 것이다.

하나하나 다 가봤는데 결국 못가는 최악의 경우를 가정하면

$T((n-3)(n-3)(n-4)(n-5)...3 \times 2 \times 1)$

$= T((n-3)(n-3)!)$

$= T(\frac{n-3}{n-2}(n-2)(n-3)!)$

$= T(\frac{n-3}{n-2}(n-2)!)$

$= O(n!)$ 이다.

그리고 $1 \le n \le 10^4$ 이니까,, 능지 머임

tip

간단한 DP로 최적화하기

최선은 아니지만 당장의 dfs를 최소한의 수정으로 AC 받게 해줌 😉

📌 무지성 DP

class Solution {
    int[] gNums;
    boolean[] memo; // true: visited
    boolean ans;

    public void dfs(int i) throws Exception {
        // base case
        if (i >= gNums.length-1) {
            ans = true;
            throw new Exception();
        }

        if (memo[i]) return;

        int mx = gNums[i];
        for (int p = 1; p < mx+1; ++p)
            dfs(i+p);

        memo[i] = true;
        return;
    }

    public boolean canJump(int[] nums) {
        gNums = nums;
        memo = new boolean[nums.length];
        Arrays.fill(memo, false);
        ans = false;
        try {
            dfs(0);
        } catch (Exception e) {
            //
        }

        return ans;
    }
}

간단한 boolean 메모이제이션을 추가해서 DP로 환승하니 285ms로 AC되었다. 이때 풀이시간은 18분 5초였음.

메모이제이션으로 인해 각 dp state를 1번씩만 계산하게 되고, state가 i로 구분되므로 시간복잡도는 $O(n)$ 이다.

함수 호출 오버헤드가 확실히 C++보다는 큰 것 같다...

📌 호출을 최소화한 DP

그래서 한번 더 최적화하여, 재귀호출이 필요없는 조건은 사전에 다 썰어보았다.

class Solution {
    int[] gNums;
    boolean[] memo; // true: visited
    boolean ans;

    public void dfs(int i) throws Exception {
        int mx = gNums[i];
        if (i+mx < gNums.length-1) {
            // rcs
            for (int p = 1; p < mx+1; ++p) {
                if (!memo[i+p]) dfs(i+p);
            }
        }
        else {
            ans = true;
            throw new Exception();
        }

        memo[i] = true; // visited
        return;
    }

    public boolean canJump(int[] nums) {
        gNums = nums;
        memo = new boolean[nums.length];
        Arrays.fill(memo, false);
        ans = false;
        try {
            dfs(0);
        } catch (Exception e) {
            //
        }

        return ans;
    }
}

...자바라 그런지 기대 이상으로 최적화 폭이 컸다. (C++은 콩알딱지만함)

실전에서 풀땐 최적화보다 가독성을 우선시하는 편이라 일단 무지성 버전으로 작성할 것 같지만,

시간이 남으면 필요없는 호출을 쳐내는 것도 꽤 괜찮아보인다.

메모

• 10분 15초만에 dfs 써서 제출했는데 틀려서 슬픔 ㅜㅜ
• 가장 최적화된 로직의 체감 난이도는 발상 측면에서 3 ~ 3.2쯤으로 느껴진다.
• 풀이 코드에서, 순회를 0 <= i < nums.length가 아닌 0 <= i < tdx 범위로 잡으면 다음의 corner case때문에 WA를 받는다.

[0]