Jump Game

Jump Game

정수 배열 nums가 제공됩니다. 처음에는 배열의 첫 번째 인덱스에 위치하며 배열의 각 요소는 해당 위치에서의 점프 길이를 나타냅니다. 마지막 인덱스에 도달할 수 있으면 true를 반환하고 그렇지 않으면 false를 반환합니다.

입출력 예제

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.

접근 방향

마지막 요소를 제외하고 주어진 배열에서 점프가 가능한 영역을 새로운 리스트에 범위로 나타내어 이 범위안에 마지막 요소가 포함될 경우 True를 반환하고 그렇지 않을 경우 False를 반환하면 쉽게 풀 수 있을 것 같았지만 제출할 때마다 만나는 통과하지 못하는 테스트케이스를 통과하기 위한 처리 로직을 하나 둘 추가하면서 마지막 코드가 완성되었습니다.

# 예를 들어, nums 배열이 [2, 3, 1, 1, 4]로 주어졌을 때,
# 첫 번째 요소 2는 2만큼 점프가 가능하므로 아래와 같은 리스트를 생성한다.
[2, 3, 1, 1, 4]
[0, 0]
# 다음 요소인 3에 도착하였을 때, 현재 위치부터 3만큼 점프가 가능하므로 위 리스트에 점프 가능 범위만큼 0을 추가한다.
[2, 3, 1, 1, 4]
[0, 0, 0, 0, 0]
# 범위를 나타내는 영역에 4가 포함되므로 True를 반환합니다.

# 두번째 예시로, nums 배열이 [1, 0, 1, 0]로 주어졌을 때,
# 첫 번째 요소 1은 한 칸만 점프가 가능하므로 아래와 같은 리스트를 생성한다.
[1, 0, 1, 0]
[0, 0]
# 하지만 도착한 요소는 0이며 다음 칸으로 진행할 수 없으므로 False를 반환한다.

나의 풀이

class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        bucket = [0] # 점프 가능한 영역을 나타내는 버킷 리스트 초기화

        # nums 배열의 길이가 1일 경우 True 반환
        if len(nums) == 1:
            return True

        # nums의 첫 요소가 0일 경우 이동 불가하므로 False 반환
        if nums[0] == 0:
            return False

        # 마지막 인덱스 요소 전까지 순회
        for i in range(0, len(nums)-1):
            # 최초 순회시 bucket 초기화 작업 수행
            if i == 0:
                for j in range(0, nums[i]):
                    bucket.append(0)
                # 만약, 현재 버킷 리스트의 길이가 nums의 길이보다 클 경우
                # 마지막 인덱스 또한 점프 가능한 영역에 포함되므로 True 반환
                if len(bucket) >= len(nums):
                    return True
                continue

            # 계산식 도출
            arange = (i + 1) + nums[i]

            # 진행 중 점프 가능 영역이 현재 요소로 제한되면서 중간 요소가 0일 경우, False 반환
            if i + 1 == len(bucket) and nums[i] == 0:
                return False

            if len(bucket) < arange:
                # 현재 영역에서 점프 가능한 범위만큼 추가로 영역을 넓히기 위해 k만큼 0을 추가(영역 확장)
                k = arange - len(bucket)
                for j in range(k):
                    bucket.append(0)

        # 점프 가능 영역을 나타내는 버킷 리스트의 길이가 nums 길이보다 클 경우 True 반환, 그렇지 않을 경우 False 반환
        if len(bucket) >= len(nums):
            return True
        else:
            return False

nums 배열을 순회하면서 해당 인덱스의 요소를 확인하고 요소만큼 점프가 가능한 영역을 나타내는 버킷 리스트를 생성하여 현재 버킷 리스트의 길이가 nums 배열의 길이보다 클 경우 마지막 인덱스가 점프 가능한 영역에 포함된다는 의미이므로 True를 반환합니다. k는 이전 요소에서 확장한 버킷 리스트의 길이에 중복을 제외하고 현재 요소에서 점프 가능한 영역을 포함시키기 위하여 arange 값에서 버킷 리스트의 길이를 차감한 값을 나타냅니다. 예를 들어 nums 배열 [3, 3, 1, 1, 4]가 주어졌을 때, i는 0부터 1까지 순회한다고 하였을 때 위 로직에 의하면 점프 가능한 영역을 나타내는 버킷은 i = 0일 때, [0, 0, 0]으로 초기화되고 i = 1일 때, 0 요소가 추가되어 [0, 0, 0, 0, 0]으로 갱신됩니다.

위 코드는 Runtime 421ms (35.14%), Memory 15.13MB (5.34%) 입니다.