[Python] LeetCode 55. Jump Game

문제 풀이

최대 점프 가능 횟수가 주어진 리스트에서 마지막 인덱스까지 이동이 가능한지 확인하는 문제이다. 간단하게 그리디 방식으로 풀었다.
for문으로 리스트를 탐색해서 이동 가능한 곳들을 모두 체크해서 마지막 인덱스까지 이동이 가능한지 확인하는 것이다.

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        leng = len(nums)
        check_list = [0] * leng
        check_list[0] = 1
        for i in range(leng):
            for j in range(1,nums[i]+1):
                if check_list[i] == 1 and i+j < leng:
                    check_list[i+j] = 1
                else:
                    break
        return check_list[-1]

처음엔 위와 같이 했지만 시간 복잡도에서 통과하지 못해서 두 번째 for문 즉, 이동 가능한 곳을 체크할 때 for문을 뒤에서부터 탐색하고, 이미 체크한 곳이면 break를 걸어 시간 복잡도를 줄여주니 문제가 해결됐다.

1. 이동 가능한 곳을 체크할 리스트를 만든다.

2. for문을 통해 리스트를 탐색한다.
   ※ 단, 이동 가능한 리스트만 탐색한다.

3. 최대 이동 가능 위치부터 역순으로 리스트의 이동 횟수 만큼 탐색하며, 이동 가능한 곳을 체크해준다.

4. 마지막 인덱스가 이동 가능하면 True 아니면 False를 return 해준다.

답

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        leng = len(nums)
        check_list = [0] * leng ## 1. 이동 가능한 곳을 체크할 리스트를 만든다.
        check_list[0] = 1
        for i in range(leng): ## 2. for문을 통해 리스트를 탐색한다.
            if not check_list[i]:
                continue
            for j in range(min(i + nums[i],leng-1), 0, -1): ## 3. 최대 이동 가능 위치부터 역순으로 리스트의 이동 횟수 만큼 탐색하며, 이동 가능한 곳을 체크해준다.
                if check_list[-1]:
                    return True
                elif check_list[j] == 1:
                    break
                else:
                    check_list[j] = 1
                
        return check_list[-1] ## 4. 마지막 인덱스가 이동 가능하면 True 아니면 False를 return 해준다.