leetcode 55. Jump Game 풀이

문제 : int로 이루어진 list의 첫번째 인덱스로 부터 출발한다. 출발점에서 인덱스 + 원소 만큼 점프가 가능하다. list의 끝에 도달할 수 있는지 여부를 boolean으로 반환하라.

Follow up :

 

아이디어 : 시작점과 끝점을 설정해서 해당 구간에서 가장 멀리갈 수 있는 점을 구한다. 다음 탐색을 직전의 끝점 + 1 에서 가장 멀리갈 수 있는 점 까지 하며 마지막 원소에 도달 할 수 있는지 탐색한다.

 

코드 :

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        if len(nums) == 1:
            return True
        def find(s, e):
            m = -1
            print(s, e)
            for i in range(s, e):
                m = max(m, (i+nums[i]))
                nums[i] = -1
            if len(nums) <= m+1:
                return True
            elif nums[m] == -1:
                return False
            else:
                s = e
                e = m + 1
                return find(s, e)
        i_s = 0
        i_e = i_s + nums[i_s] + 1
        if len(nums) <= i_e:
            return True
        ans = find(i_s, i_e)
        return ans
        

학습 포인트 :

첫번째 원소부터 추적했을 때 상당한 시간과 메모리가 소요된다. 다른 사람의 코드를 보면 마지막 원소에 도달한 것을 전제로 시작하여 실제 도달했는지를 추격한다. 이 경우 시간과 메모리를 크게 아낄 수 있다.

문제를 풀 때 이렇게 결과로 부터 거꾸로 생각하는 능력을 키우면 좋겠다.

 

다른 사람의 코드 :

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # Concept - Instead of starting from the first element of the
        # Array, think if you have already reached the end, Now check
        # from where have you reached there. In the end your destination
        # should be equal to 0 as we needed to start from first index
        destination = len(nums)-1
        source = destination-1

        while source >= 0:
            if source + nums[source] >= destination:
                destination = source
                source-=1
            else:
                source-=1
        return destination == 0

 

출처 : leetcode.com/problems/jump-game/submissions/