[python3] 45. Jump Game II

풀이 일자: 23.02.08

난이도: [Medium]

분류: [Array, DP, Greedy]

문제 내용

 

인덱스 0부터 시작하는 arr가 주어졌을 때 arr[i]의 의미는 i번째 칸에서 오른쪽으로 움직일 수 있는 최대 길이를 의미한다. 이 경우 인덱스 n-1에 도달하기 위해 움직여야할 최소 횟수를 구하는 문제이다.

 

아래의 그림을 보면 알 수 있다. 아래의 배열이 주어졌을 때 2번의 이동으로 배열의 맨 끝까지 이동이 가능하다.

문제 해결 흐름

1. 어떤 알고리즘으로 해당 문제를 해결하면 좋을까?

→ 0번째에서 n-1까지 이동해야하므로 최대한 멀리 갈 수 있는 node를 찾아서 그런 node를 타고 다니면 되겠다. 

→ 즉 멀리 갈 수 있는 것만 택하면 되니까 Greedy하게 처리하면 되겠네..

 

2. 그렇다면 각각의 위치에서 갈 수 있는 최대 위치를 알아둬야겠네.

→ 기존의 배열의 값과 각각의 값이 위치한 index를 더하자.

 

3. 특수 케이스가 있나?

→ 배열의 길이가 1일때는 굳이 움직일 필요가 없겠네. return 0;

 

4. 결과 찾기

→ 내가 갈 수 있는 범위 내에서 가장 멀리 갈 수 있는 곳으로 이동하면 되겠다.

class Solution:
    def jump(self, nums: List[int]) -> int:
        ans = 0;

        for i in range(len(nums) - 1):
            nums[i] += i;

        nums[-1] = len(nums) - 1;  # 마지막 index은 상관없으므로 (배열의 길이 -1)로 설정
        pos = 0;

        if len(nums) == 1:			# 배열의 길이가 1이라면 0을 리턴(움직이지 않아도 됨)
            return 0;

        while(1):
            maxpos = nums[pos];		# 현재 위치에서 가장 멀리 갈 수 있는 곳의 idx
            if maxpos >= (len(nums) - 1):	# 만약 해당 idx가 (배열의 길이 -1)과 같거나크면
                ans += 1;					# 바로 도착 완료
                break;
            pos = nums.index(max(nums[pos + 1: maxpos + 1]));
            ans += 1;		# 도착점에 도착할 수 없다면 현재 위치에서 이동가능한 곳 중
					# 가장 멀리 갈 수 있는 곳의 idx를 저장하고 해당 위치로 이동
        return ans;

=> Greedy를 사용해야 한다는 점을 파악해서 사용하였지만 while문과 배열의 index, max함수로 거의 N^3정도의 Time complexity로 비효율적인 알고리즘.

 

Time Complexity: O(N^3)

바깥의 while문과 index와 max 메소드를 중첩해서 사용하고 있기 때문에 일반적으로 O(N^3)의 시간복잡도를 가질 것이다.

다만 극단적의 배열 내의 숫자가 크거나 작다면 while문과 max메서드가 돌려야 할 원소 수는 반비례 관계이므로 O(N^2)에 가까울 것이다. ( jump의 크기가 크면 while문은 그만큼 적게 돌아갈 것이고 max는 jump의 크기가 큰 만큼 해당 범위 원소를 순회해야하기 때문에 반비례 관계이다.)

 

Space Complexity: O(1)

pos와 ans외에 기존에 주어진 배열내에서 in-place로 진행했기 때문에 O(1)의 공간복잡도를 가진다. 

 

 

다른 해결 방식

1. Greedy를 사용하되 탐색을 한 번만 진행해서 시간복잡도를 줄일 수 있지 않을까? (Official Solution)

 

[방법]

far: 각 위치에서 갈 수 있는 지점의 최댓값

end: 현재 점프에서 갈 수 있는 최대의 위치

 

현재위치와 end가 같아질 때 == 이전 jump에서 갈 수 있는 최대거리에 도달했을 때

 end에 far값을 넣는다는 의미 ==  다음 jump를 가장 멀리 뛸 수 있는 far위치로 end를 설정한다는 의미

 

1. 기존의 배열을 가져온다.

2. 현재 위치에서 갈 수 있는 최대 index를 구해 far이라 설정한다.

3. 현재 index가 end와 같다면 end에 far값을 넣는다.

4. i를 증가시키고 2와 3을 반복한다.

class Solution:
    def jump(self, nums: List[int]) -> int:
        answer, n = 0, len(nums)
        end, far = 0, 0
        
        for i in range(n - 1):
            far = max(far, i + nums[i])

            if i == end:
                answer += 1
                end = far
                
        return answer

Time Complexity: O(N)

for문 하나만 돌아가고 있기 때문에 시간복잡도는 O(N)이 될 것이다.

 

Space Complexity: O(1)

end와 far외에 기존에 주어진 배열내에서 in-place로 진행했기 때문에 O(1)의 공간복잡도를 가진다. 

 

 

그 외에도 AlecLC를 닉네임으로 사용하는 분이 recursive backtracking, top-down dp, bottom-up dp, greedy로 푼 풀이과정이 존재한다. 궁금하다면 직접 확인해보면 좋을 것 같다.

https://leetcode.com/problems/jump-game-ii/solutions/3076867/jump-game-ii/

Official Solution - Jump Game II - LeetCode

 

 

문제 링크

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

Jump Game II - LeetCode