[Leetcode 아주 상세한 문제풀이] 55. Jump Game – 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 55번 문제 Jump Game 이다.

우선 문제를 살펴보자.

 

리트코드 55번 문제 Jump Game 링크

Jump Game - LeetCode

Jump Game - LeetCode

 

 

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.

Example 1:
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:
Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
 
Constraints:
1 <= nums.length <= 104
0 <= nums[i] <= 105

 

 

문제 설명

문제를 간략히 살펴보자. 인풋으로 정수로 이루어진 배열이 주어진다. 이때 주어진 배열의 element들은 그 위치에서의 '최대' 점프 거리를 나타낸다. 이때 점프거리라는 것은 배열에서 오른쪽 방향으로 이동할 수 있는 인덱스 거리를 의미한다. 또한 '최대'라고 명시되어 있으므로 만약 element 값이 2라면 1만큼 뛰어도 되고 2만큼 뛰어도 된다. 문제에서 요구하는 바는 주어진 배열의 첫번째 인덱스에서 시작해 배열의 마지막에 도착할 수 있는지 알아보라는 것이다.

문제 예시 1번을 살펴보면 인풋으로 [2, 3, 1, 1, 4]라는 배열이 주어졌다. 우리는 첫번째 인덱스 (element=2)에서 시작해 마지막 인덱스 (element=4)까지 도달할 수 있는지 판단해야 한다. 첫번째 인덱스의 element 값이 2이므로 최대 2만큼 점프를 뛸 수 있다. 우리는 우선 1만큼 점프를 뛰어 두번째 인덱스 (element=3)으로 이동할 수 있다. 그 후 3만큼 점프를 뛰면 배열의 마지막 인덱스에 도달할 수 있다. 따라서 이 경우 'true'를 리턴하면 된다. 이제 문제를 풀어보자.

 

 

문제 접근법

이 문제를 해결하기 위해 우리는 greedy algorithm을 이용할 것이다.

핵심 아이디어는 주어진 배열을 탐색할 때 가장 멀리 도달할 수 있는 인덱스를 확인하는 것이다.

특정 지점에서 점프를 해 가장 멀리 도달할 수 있는 인덱스가 배열의 마지막 인덱스보다 더 뒤에 있다면 우리는 점프를 '덜' 함으로써 마지막 인덱스에 도달할 수 있다.

반대로 특정 지점에서 점프를 해 가장 멀리 도달할 수 있는 인덱스가 배열의 마지막 인덱스보다 더 앞에 있다면 마지막 인덱스에 도달할 수 없다는 얘기가 된다.

좀 더 자세히 다음과 같은 과정을 거치게 된다.
우선 주어진 배열의 element들을 차례로 탐색한다.

이때 변수를 하나 만들어 탐색하고 있는 element에서 가장 멀리 도달할 수 있는 인덱스를 확인한다.

만약 현재 탐색하고 있는 인덱스가 지금까지 확인된 최대 도달 거리보다 큰 경우 그곳까지 도달할 수 없다는 얘기가 된다.

따라서 이 경우 false를 리턴하고 종료하면 된다.

반대로 현재 탐색하고 있는 인덱스가 지금까지 확인된 최대 도달 거리보다 작은 경우 그곳까지 도달할 수 있다.

따라서 이 경우 최대 도달 거리를 현재 탐색 인덱스 + jump (그 인덱스의 element 값)으로 업데이트 해준다.

이 과정을 거치는 와중에 최대 도달 거리가 주어진 배열의 마지막 인덱스보다 같거나 크다면 마지막에 도달할 수 있다는 얘기다.

따라서 이 경우 true를 리턴하고 종료하면 된다.

이제 코드로 한 번 살펴보자.

 

 

문제 풀이

배열을 입력받기 위한 함수를 정의해 준다. (line 1)

최대 도달 거리를 트랙킹 하기 위하여 변수를 만들어 주고 0으로 초기화 한다. (line 2)

우리는 주어진 배열을 처음부터 for loop를 이용하여 탐색한다. (line 3)

위에서 설명한대로 현재 탐색 인덱스가 최대 도달 거리보다 크다면 false를 리턴하고 종료한다. (line 5-6)

그렇지 않은 경우 최대 도달 거리를 업데이트 해준다. (line 8)

이때 업데이트는 지금까지의 최대 도달 거리와 현재 탐색 인덱스+jmp (그 인덱스의 element 값) 중 더 큰 값을 취한다.

마지막으로 최대 도달 거리가 주어진 배열의 마지막 인덱스보다 같거나 큰지 확인한다. (line 10)

만약 그 값이 마지막 인덱스보다 같거나 크다면 배열의 마지막에 도착할 수 있으므로 true를 리턴하고 종료한다. (line 11)

주어진 배열을 모두 탐색했는데도 불구하고 true나 false가 출력되지 않았다면 어쨋든 배열의 마지막에 도달할 수 없는 경우이므로 false를 리턴하고 종료한다. (line 12)

 

 

문제 풀이 코드

def canJump(nums):
    max_reachable = 0
    for i, jump in enumerate(nums):
        # If the current index is beyond the maximum reachable index, return False
        if i > max_reachable:
            return False
        # Update the maximum reachable index
        max_reachable = max(max_reachable, i + jump)
        # If the maximum reachable index is at least the last index, return True
        if max_reachable >= len(nums) - 1:
            return True
    return False
 
# Test the function with the provided examples
print(canJump([2,3,1,1,4]))  # Output: True
print(canJump([3,2,1,0,4]))  # Output: False
 

 

 

관련 문제

리트코드 62번 Unique paths 문제 풀이 링크

리트코드 70번 Climing stairs 문제 풀이 링크

리트코드 91번 Decode ways 문제 풀이 링크

리트코드 139번 Work break problem 문제 풀이 링크

리트코드 198번 House robber 문제 풀이 링크

리트코드 213번 House robber II 문제 풀이 링크

리트코드 300번 Longest increasing subsequence 문제 풀이 링크

리트코드 322번 Coin change 문제 풀이 링크

리트코드 1143번 Largest Common Subsequence 문제 풀이 링크

 

 

55. Jump Game