55. Jump Game (Medium) [Python]

문제

 

💡 생각 방식

당장 있는 index에서 제일 멀리 도달할 수 있는 index가 뭔지 일단 본다

그리고 loop을 돌려서 마지막까지 도착할 수 있는지 코드를 짜본다 

 

💻 코드

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        max_reachable = 0

        for i in range(n):
            if i > max_reachable:
                return False
            elif max_reachable == n:
                return True
            max_reachable = max(max_reachable, i + nums[i])
        return True

 

* max_reachable = 0   [최대 도달 가능한 index]

 

* if문 설명

만약에 현재 내가 있는 index가 현재까지 최대 도달 가능한 index인 max_reachable보다 크다면, 현재 위치는 전에 점프로 도달이 불가능하다, 그러므로 False를 리턴해주면 끝난다

또는, 만약 loop를 다 돌리기 전에 마지막까지 도달할 수 있으면 True를 리턴해주고 끝난다. 이렇게 한다면 효율이 좀 더 좋아진다고 생각한다. 왜? 만약 이미 가능하다는 정답이 나왔다면 굳이 나머지를 돌릴 필요가 없기 때문에 (밑에 예시 참고)

 

* max_reachable = max(max_reachable, i + nums[i]) 설명

최대 도달 가능한 index -> max_reachable를 업데이트해준다

이게 무슨 말인지는 그림으로 설명하는 게 좋을 것 같다

 

현재 max_reachable = 2이다.

그리고 보다시피 index 2인 0이라는 숫자까지 갈 수 있다

여기서 우리가 2번째 루프 즉 i = 1을 돌릴 때, 우리는 index 1에서 3을 점프할 수 있다는 것을 확인할 수 있다. 즉 4번 index까지 갈 수 있는 셈이다.

그러니 우리가 도달 가능한 index는 4번 즉 마지막 index인 5이다. (index 0 -> 1 -> 4, 끝)

 

결과

⭐️다른 방법

https://www.youtube.com/watch?v=Yan0cv2cLy8&ab_channel=NeetCode

 

이 유튜버의 경우 배열의 뒤에서 시작해서 마지막에 도달해야 하는 index를 점차 앞으로 당기는 방법이다

어떤 상황에서 뒤에서 시작하는 게 좋은지 모르겠지만 난 내 코드의 접근 방식이 좀 더 직관적이라고 생각한다

 

여담으로 문제를 풀기 전에 false가 나오는 간단한 test case를 먼저 만드는 습관이 있는데 일단은 이런 사고방식이 나는 문제를 풀 때 더 도움이 되는 것 같다.