[Leet code - 55] Jump Game ✅

Jump Game - LeetCode

 

문제

Input : 정수 배열 nums, 각 원소는 다음 원소로 이동할 수 있는 최대치를 의미

Output : 이동을 하여 배열의 끝까지 도달할 수 있는지에 대한 bool값

 

시간 복잡도

※1초에 1억번을 대략적인 기준으로 삼는다.

 

$1 \le n \le 10'000$ 으로 $n \log n$이하의 복잡도를 목표로 잡으면 된다.

 

해결 과정

처음에는 완전탐색밖에 생각이 안났었는데, 왜냐하면 어떤 발판을 선택해야하는지에 대해 접근하고 있었기 때문인 것 같다..

그러다 어떤 원소에서 최대치를 이동하면 그 이전까지의 원소들은 이동이 가능하다는 것에 초점을 맞춰 범위적으로 접근했다.

 

핵심 아이디어는 시작 index와 이동 가능한 최대 index를 저장하여 순회하는 것이다.

순회하면서 가장 멀리 가는 index를 저장하여 또 이전 범위 이후부터 가장 멀리 가는 index까지 순회하는 것을 반복한다.

 

사전에 작성한 대략적인 로직 순서다.

1. 현재 index (a)
2. a에서 가장 많이 이동 가능한 index 저장 (b)
3. a에서 b까지 제일 많이 이동 가능 한 index 저장(c)
4. a와 b를 업데이트 (a = b + 1, b = c)
5. input.size - 1 <= b면 true

 

 

구현

bool canJump(vector<int>& nums) {
    
    int a = 0;
    int b = nums[0];

    while (a <= b)
    {
        if (nums.size() - 1 <= b) return true;

        int c = 0;
        for (int i = a; i <= b; ++i)
        {
            // out of range에 대해 안전함.
            c = std::max(c, i + nums[i]);
        }

        a = b + 1;
        b = c;
    }

    return false;
}

 

 

개선 코드

나는 시작부터 끝으로 향하는 forward방식을 생각했지만, 뒤에서부터 시작으로 향하는 backward 방식도 있다.

해당 방법은 코드가 깔끔하다! (물론 복잡도는 $O(n)$으로 동일함)

bool canJump(vector<int>& nums) {
    int goal = nums.size() - 1;

    for (int i = nums.size() - 2; i >= 0; i--) 
    {
        if (i + nums[i] >= goal) 
        {
            goal = i;
        }
    }

    return goal == 0;        
}

 

 

뒤에서부터 계산하여 도달할 수 있는지 확인하고 도달가능하다면 해당 자리를 goal지점으로 만들어버린다.

그래서 기존 목표 index를 배열의 마지막 원소에서 점차 줄여가는 방식이다.