Algorithm 8

1. 내 풀이

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        my_list = []
        # 1. list에 0이 없으면 True
        if 0 not in nums:
            return True
        
        # 1. list에 0이 있는 경우
        for i in range(len(nums)):
            # 2. 리스트 인덱스 번호 + 인덱스의 값 저장
            my_list.append(i+nums[i])
            if nums[i] == 0:
                # 3. my_check_list 초기화
                my_check_list = []
                
                # 2. 리스트 인덱스 번호 + 인덱스의 값 비교
                if max(my_list) > i:
                    my_check_list.append('T')
                elif max(my_list) == i:
                    if i == len(nums)-1:
                        my_check_list.append('T')
                        
                # 3. 리스트에 0이 여러개 있는 경우 
                if 'T' not in my_check_list:
                    return False
                    
        # 3. 리스트에 0이 여러개 있는 경우             
        if 'T' in my_check_list:
            return True

방법

• 리스트에서 0을 만난 경우 그 0을 넘어갈 수 있는지 없는지를 판단하여 0을 넘어갈 수 없으면 False
• 0을 넘어갈 수 있는지 없는지에 대한 판단 --> (인덱스 번호 + 인덱스 값)과 0의 인덱스 번호를 비교
• 리스트에 0이 여러개 있는 경우의 처리를 위하여 체크를 여러번 진행

(1) list에 0이 있는지 없는지 판단

리스트에 0이 없는 경우는 모두 인덱스의 끝까지 도달 할 수 있으므로 그 경우 True를 return하도록 하였다.
그러한 경우를 먼저 처리하여 리스트에 0이 없는 경우에 대해서만 연산을 진행하도록 하였다.

(2) 인덱스 번호 + 인덱스 값 비교

먼저 리스트의 인덱스 번호 + 인덱스의 값을 연산한 후, 만들어 두었던 리스트에 추가하였다.
리스트에서 0을 만나면 <0의 인덱스 번호 (i)> 와 <인덱스 번호 (i) + 인덱스 값 (nums[i])>을 비교한다.

비교는 리스트에 추가된 값 중 가장 큰 값과 비교

• 인덱스 번호 + 인덱스 값 > 0의 인덱스 번호
  0을 뛰어넘을 수 있으므로 True

• 인덱스 번호 + 인덱스 값 = 0의 인덱스 번호
  0이 리스트의 맨 뒤에 있으면 이 경우도 True
  그렇지 않은 경우 0을 뛰어넘을 수 없으므로 False
  

• 인덱스 번호 + 인덱스 값 < 0의 인덱스 번호
  0을 뛰어넘을 수 없으므로 False

(3) 리스트에 0이 여러개 있는 경우

리스트에 0이 여러개 있는 경우를 확인하기 위해서 my_check_list를 만들었다.
만약 True인 조건이 있으면 list에 'T'를 추가한다.

리스트에 'T'가 없으면 0을 뛰어넘을 수 있는 경우의 수가 없으므로 False를 return
for문을 돌고나면 my_check_list 초기화하였다.

for문을 다 돌았을 때 마지막으로 True, False를 확인한다.

2. 다른 풀이

다른 풀이는 이 블로그에서 가져왔다.

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # approach: start from last index to iterate list and check if 
        #           the left-most point which can reach it is start index

        n = len(nums)
        if n <= 1:
            return True

        lastPoint = n - 1
        for i in range(n - 1, -1, -1):
            if i + nums[i] >= lastPoint:
                lastPoint = i

        return lastPoint == 0

방법

• list에 값이 하나만 있는 경우 True

• 리스트의 마지막부터 확인하는 방식

• 인덱스 값 + 인덱스 번호와 lastPoint를 비교 --> 크거나 같으면 lastPoint에 도달할 수 있으므로

• lastPoint에 도달하면 lastPoint의 값을 변경 --> 0에 도달(첫번째 지점)까지 오면 True

3. 다른 풀이 2

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        num = 0
        for i in range(len(nums)):
            if i<=num:
                num = max(nums[i]+i,num)
                if num>=len(nums)-1:
                    return True
        return False

방법

인덱스 값 + 인덱스 번호와 리스트 길이를 비교