[ leetcode 문제풀이 ] Jump Game

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

Jump Game - LeetCode

(Jump Game 문제는 위 링크에서 풀어보실 수 있습니다.)

 

 

 

< Jump Game 문제 설명 >

 

Jump Game 문제는 다음과 같다.

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.
Return true if you can reach the last index, or false otherwise.

 

주어진 정수 배열 nums의 각 원소는 해당 위치에서 jump 할 수 있는 최대 길이를 나타낸다. 최초로 배열의 첫 index에 배치된다고 할 때 jump를 통해 마지막 index에 도달할 수 있으면 true를, 그렇지 않으면 false를 리턴하여라.

 

다음 두 가지 출력 예시가 주어졌다. 

 

주어진 제한 조건은 1 ≤ nums.length ≤ 10^4 와 0 ≤ nums[i] ≤ 10^5 이다.

 

 

 

---

< Jump Game 문제 접근(1) >

 

우선 완전 탐색의 방법으로 접근하였다.

주어진 nums의 뒤에서부터 index의 역순으로 가능한 jump의 크기를 모두 훑으며(1 ~ nums[i]) canJump 여부를 메모이제이션 하였다. 최종적으로 첫 번째 index에 대한 canJump 값을 리턴하도록 하였다. 코드로 보면 다음과 같다. (Cpp 사용)

 

bool canJump(vector<int>& nums){
    int n = nums.size();
    vector<bool> cache(n);

    cache[n-1] = true; 		// 마지막 index에 도달 -> true
    for(int i = n-2; i>-1; i--)
        for(int j = 1; j<=nums[i];j++)
            if(cache[i+j] == true){
                cache[i] = true;
                break;
            }
    return cache[0];
}

 

runtime이 873 ms(faster than 7.47%)으로 오래 걸렸고 memory usage 면에서도 48.5 MB(less than 20.25%) 아쉬운 성능을 보여주었다. 아무래도 완전탐색을 진행하다 보니 n=nums.length, m = max(nums[i])이라 할 때 O(nm)의 시간복잡도에 의해 발생하는 문제 같다. 더 빠른 방법이 존재하는 것으로 보인다.

 

 

 

---

< Jump Game 문제 접근(2) >

 

nums[i]가 최대로 jump 할 수 있는 길이를 나타내기에 nums[i]만큼 jump해서 마지막 index를 넘었다면 0 < k < nums[i]인 어떤 k만큼 jump해 마지막 index에 위치하도록 할 수 있을 것이다. 따라서, greedy algorithm을 사용해 1 ~ nums[i] 에 대한 반복 없이 푸는 방법을 구상하고자 하였다.

 

작성한 알고리즘은 다음과 같다. (Cpp 사용)

 

bool canJump(vector<int>& nums) {
    int n = nums.size();
    if(n == 1) return true;
        
    vector<bool> can_jump(n-1,true); // true는 탐색하지 않은 경우(default임)
    int curr = 0;
    do{
        if(curr+nums[curr] >= n-1) return true;
        if(nums[curr] == 0 || !can_jump[curr+nums[curr]])
            can_jump[curr--] = false;
        else if(can_jump[curr+nums[curr]]) curr += nums[curr];
    }while(curr > 0);
    return false;
} // runtime : 68 ms (faster than 80.59 %), memory usage : 48.7 MB (less than 16.75 %)

 

최대한 멀리 뛴 후 더 이상 뛸 수 없는 경우(nums[i] == 0) 한칸씩 왼쪽으로 옮겨가며 다시 탐색한다.

memory usage가 아쉬운 것으로 보아 can_jump라는 메모이제이션 없이도 풀 수 있는 것 같았다. 

 

이런 고민을 직접 해결하진 못했고 leetcode discussion에서 도움을 받았다. 아래 코드가 그것이다. (Cpp 사용)

 

bool canJump(vector<int>& nums) {
    int n = nums.size();
        
    int reach = 0;
    for(int curr = 0; curr <= reach && curr<n;curr++){
        reach = max(reach, curr + nums[curr]);
        if(reach >= n-1) return true;
    }
    return false;
} // runtime : 56 ms (faster than 93.69 %), memory usage : 48.3 MB (less than 86.05 %)

 

이렇게 간단한 걸 왜 생각 못했나 싶다..! (T.C. : O(n), S.C. : O(1))