[LeetCode 풀이/python] 55. Jump Game (medium)

문제 설명: 0 이상의 정수 배열 nums 가 주어지고, 초기 위치는 해당 배열의 첫번째 인덱스로 설정되어 있다. 배열의 각 요소가 해당 위치에서 가능한 최대 점프 길이를 나타낸다고 할 때, 가장 마지막 인덱스에 도달할 수 있는지를 확인하시오.

 

(Given an array of non-negative integers nums, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index.)

 

예시 1)

입력: nums = [2,3,1,1,4]  -->  출력: true

설명: 인덱스 0 에서 1로 1 칸 점프 후, 인덱스 1에서 마지막 인덱스(4) 로 3 칸 점프

 

예시 2)

입력: nums = [3,2,1,0,4]  -->  출력: false

설명: 인덱스 0 에서 어떤 길을 거쳐도 항상 인덱스 3에 도착하게 되나, 인덱스 3에서의 최대 점프 길이가 0 이므로 마지막 인덱스(4) 로 갈 수 없음

 

제한 조건:

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

------ * ------ * ------ * ------

 

[풀이 1안] -- not a solution

• 접근법
  • 초기 설정된 맨 첫번째 인덱스에서부터 탐색(점프) 가능한 범위에 대해 백트래킹을 이용해 탐색 & 마지막 인덱스에 도달 가능하면 res 에 카운트 추가
  • 백트래킹은 기본적으로 recursive 구조이다보니 마지막 인덱스에 도달한 경우 return True 를 하더라도 탐색이 끝나지 않아 True flag 를 유지하기가 어렵다는 점... @_@  (광역 변수 같은 개념이 이를 위해 쓰이는 걸까...)

 

• 코드 구현

def canJump(nums: List[int]) -> bool:
    res = []
    target = len(nums)-1
    dfs(nums, 0, target, res)
    if len(res) > 0: return True
    else: return False
    
def dfs(nums, start, target, res):
    if start + nums[start] >= target:
        res.append(1)
        return 
        
    for i in range(start+1, start+nums[start]+1):
        if len(res) == 1: break
        dfs(nums, i, target, res)

 

• 결과
  • 시간 제한이 없으면 답이 틀리진 않을 것 같은데 Time Limit Exceed Error 로 인해 통과 못함 ㅠ_ㅠ
  • 도달 가능한 모든 경우를 찾는 것이 아니라 일단 하나만 찾는 순간 탐색을 끝내면 되는데 백트래킹 알고리즘을 쓰게 되면 불필요한 탐색을 진행하게 되는 것이 문제인 듯...!

 

 

[풀이 2안]

• 접근법
  • 마지막 인덱스에서부터 역순으로 탐색하며, 점프할 때마다 타겟 인덱스도 업데이트 함에 따라 탐색 범위를 줄여 나간다...!
  • True 를 리턴하게 되는 조건이 최종적으로 인덱스 0 으로 도달하는 것임을 이용해서, True / False 변수 target 을 이용해서 나타낸 것이 매우 인상적인 풀이...!!

 

• 코드 구현

def canJump(nums):
    target = len(nums) - 1
    
    for i in range(len(nums))[::-1]:
        if i + nums[i] >= target:
            target = i
            
    return not target

 

• 결과
  • 시간 복잡도 O(n) 으로 통과 ~_~