LeetCode 55. Jump Game

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.

 

 

 

풀이

 

문제를 보고 bfs를 사용해야겠다고 생각했다.

 

class Solution(object):
    def canJump(self, nums):
        n =len(nums)
        visit = [0] * (n)
        result = False
        q= []

        q.append(0)
        visit[0] = 1
        while q:
            node = q.pop()
            if node == n-1:
                result =True
                break
            for i in range(1,nums[node]+1):
                if node+i <n and visit[i+node] ==0:
                    print(node+i)
                    visit[i+node]=1
                    q.append(node+i)
        return result
        
        
 #sudo
 
 list = [1,1,2,3,4]
 최초 0번 인덱스에서 시작

 방문리스트 생성 = [0] *(n)
 q =[0] bfs를 시작할 리스트
 while q가 0이 될 때 까지
 	q.pop() q에 담긴 원소 꺼내기
    for i in range(list[q.pop()]) 큐에 담긴 원소를 list인덱스 값을 for문 range(범위)로 지정
   		if 현재인덱스 + i < 리스트의 원소 개수 and  visit[현재인덱스+i]==0 방문하지 않았다면:
        	q.append(i+현재인덱스)

문제를 해결하긴 했으나 속도나 성능이 굉장히 낮은 편이었다. 

 

 

다른사람이 dp를 이용해 풀이한 방법 

#dp를 통해 푼 풀이법

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        dp = [False] * n
        dp[n-1] = True
        for i in range(n-2, -1, -1):
            for j in range(i+1, min(n, i+nums[i]+1)):
                if dp[j]:
                    dp[i] = True
                    break
        return dp[0]

하향식 dp를 통해서 문제를 해결했다 . dp로 푸는 방식이 확실히 성능면에선 뛰어났다 .