LeetCode Top Interview 150) Jump Game

Question

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.

Constraints:

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 10^5

class Solution:
    def canJump(self, nums: List[int]) -> bool:

---

---

정수 리스트nums가 있고, 인덱스에 저장된 값 이하의 범위로 다음 인덱스로 이동할 수 있습니다. 그렇게 마지막 인덱스까지 도달할 수 있는지 bool값을 반환하는 문제입니다. 만약 특정 리스트의 원소 값이 0이라면 해당 인덱스에선 이동하지 못합니다.

제가 생각한 코드는 다음과 같습니다.

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        zero_idx = None
        now_idx = len(nums)-1
        if nums[-1] == 0: # 끝이 0인 경우
            now_idx -=1
        if nums[0] == 0: # 시작이 0인 경우
            return False if len(nums)>1 else True

        while now_idx >= 0:
            if nums[now_idx] == 0:
                zero_idx = now_idx
                now_idx-=1

                while nums[now_idx]+now_idx <= zero_idx:
                    if now_idx == 0:
                        return False
                    now_idx-=1
            else:
                now_idx-=1
                
        return True

• zero_idx : nums리스트를 탐색하는 도중 0이 나온 지점의 인덱스를 저장하는 변수.
• now_idx : 탐색하는 지점의 인덱스 변수. 역순으로 탐색할 예정이므로 len(nums)-1로 초기화.
• 예외 상황을 미리 처리합니다. 대부분의 상황에서는 0을 넘지 못한다면 False지만,
  • 마지막 0이라면 마지막을 넘지 못하는건 제외해야 하므로 끝에서 두번째 인덱스에서 시작합니다.
  • 또는 시작이 0이라면 원래 False입니다. 하지만 길이가 1이면 마지막 원소에 도달한 상태이므로 True를 반환합니다.
• 뒤에서부터 첫 원소까지 역순회합니다.
• 역순회 중 0이 나타나면 zero_idx에 인덱스를 저장하고 다음 원소로 넘어갑니다.
  • 이후로 나오는 값들이 zero_idx를 넘는 값을 가질때까지 새로운 내부 whlie문에서 역순회를 이어갑니다.
    • 만약 끝까지 zero_idx를 넘는 원소가 나타나지 않는다면 False를 반환합니다.
  • zero_idx를 넘는 원소가 나왔다면 내부 while문을 벗어나면서 다시 외부 while문으로 이동합니다.
• 첫번째 원소까지 모두 순회하고 외부 while문을 벗어난다면 True를 반환합니다.

이 문제에 대해 고민할 때 제가 생각한 포인트는 결국 0값을 가지는 지점을 뛰어넘을수 있는가가 요점이라는 생각을 했습니다.

따라서 0이 나오는 지점을 확인하기 위해 zero_idx를 두었고 이전의 지점들이 zero_idx를 넘는다면 해당 0값은 지날 수 있다고 여겼습니다.

이 방식으로 모든 0을 넘는다면 while문을 모두 탈출하여 True를 반환하도록 코딩했습니다.

역순으로 한 이유는 한 방향으로 한 번에 마무리를 생각했기 때문입니다.

근데 지금 다시 생각해보니 순방향도 가능하겠네요..? 그냥 순방향으로 돌면서 최대로 이동할 수 있는 값을 업데이트하면 되겠네요.. 더 쉬운거 같다.....

생각난 김에 코드를 작성해봤습니다.

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        if nums[0] == 0: # 시작이 0인 경우
            return False if len(nums)>1 else True

        if nums[-1] == 0: # 끝이 0인 경우
            nums = nums[:-1]

        possible_max_idx = 0

        for idx,num in enumerate(nums):
            if possible_max_idx < idx+num:
                possible_max_idx = idx+num
            if num==0 and possible_max_idx <= idx:
                return False
        return True

음... 이렇게 하니까 진짜 된다.. 성능도 별 차이없네요..

앞에서부터 최대로 이동 가능한 지점을 갱신하면서 0이 나올때 최대 지점이 0을 못넘는다면 False를 반환하고 반복문이 끝나면 True를 반복하게 하니까 됩니다.

웃프다..