LeetCode (C/C++) 55. Jump Game

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

---

풀이 1

일단 떠오른 대로 풀었다.

큐(q)에 현재 지점부터 갈 수 있는 모든 지점을 넣어두고 해당 지점들에서 끝까지 갈 수 있는지 확인하였다.

이렇게 푸니 무려 2초가 나옴...

 

풀이 2

DP인 건 알겠지만 못 풀겠어서 답을 봤고, 뒤에서부터 탐색하는 방법으로 풀었다. 

next 변수를 현재 지점에서 갈 수 있는 곳으로 지정해두고 마지막 - 1번째 인덱스에서부터 앞으로 탐색한다.

현재 지점에서 next까지 갈 수 있다면 next의 위치를 현재 지점으로 앞당겨 저장하고,

다시 앞으로 탐색하며 0번째 지점에서 next 지점에 닿을 수 있는지를 확인한다.

이렇게 하면 모든 지점을 탐색하기에 3칸 + 0칸 < 2칸 + 2칸처럼 현재 스텝은 적었음에도 마지막에 더 멀리 도착하는 케이스를 확인할 수 있다.

dp 배열을 사용해도 좋지만 마지막 next가 0인지를 확인하면 dp 배열을 사용하지 않을 수 있다.

 

이 방법을 몰라서 n제곱으로 풀었다.. dp의 세계는 너무 넓고 다양한 것ㅠ

---

코드 1

class Solution {
public:
    bool canJump(vector<int>& nums) {
        queue <int> q;
        bool visited[10000] = {true, false, };
        int end = nums.size() - 1;
        
        q.push(0);
        while (!q.empty()) {
            int now = q.front();
            q.pop();

            // 현재 지점에서 끌가지 갈 수 있다면 true 반환
            int endIdx = min(end, now + nums[now]);
            if (endIdx == end)
                return true;

            // 시작지점 ~ 갈 수 있는 지점 다 queue에 넣기
            for (int i = 0; i <= endIdx; i++) {
                if (visited[i]) continue;
                
                visited[i] = true;
                q.push(i);
            }
        }
        return false;
    }
};

 

코드 2

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size(), next;

        next = n - 1;
        for (int i = n - 2; i >= 0; i--) {
            if (next <= i + nums[i])
                next = i;
        }
        return next == 0;
    }
};