Python으로 푸는 LeetCode 55. Jump Game (Medium)

nums 배열에는 현재 index부터 이동가능한 최대 길이값이 들어 있다.

Index 0부터 맨 마지막 Index까지 도달이 가능한지 알아보는 프로그램을 짜시오.

Leetcode에서 푼 문제 리스트 보기

LeetCode에서 문제 보기

github에서 코드 보기

문제 풀이

visited를 활용하기 - Time Limit exceeded

현재 위치에서 nums 배열에 적인 숫자 이하 만큼 이동 가능한 지점들을 이전에 접근했던 곳인지 확인한다. 아직 방문하지 않은 새로운 지점일 경우에는 방문 표시를 해주고 schedule에 넣어서 그 위치에서 nums에 적인 수만큼 최대 이동 가능한 모든 지점이 아직 유효한 지점인지 반복문을 활용해서 푸는 방법이다. 하지만 이 방법을 이용할 경우에는 시간 초과 문제가 발생한다.

이동 가능한 index만으로 문제 풀기

주어진 nums 를 모두 순회한다. 현재의 index에서 nums에 적힌 숫자만큼 이동 가능하다. 순회를 거칠때마다 가장 멀리 이동 가능한 avail_index를 구해 업데이트 해둔다. 현재의 index가 avail_index보다 클 경우에는 더이상 순회가 불가능하므로 False를 리턴해준다. 만약 모든 nums를 순회했는데도 맨 마지막 index에 도달하지 못해도 False를 리턴한다. True를 리턴하는 경우는 avail_index가 마지막 index보다 크거나 같을 경우이다. 이 방법을 사용하면 O(len(nums)) 시간이면 반드시 결과를 알 수 있다. 

파이썬 코드 - visited[] 활용

class Solution:
    def canJump(self, nums) -> bool:
        length = len(nums)
        if length == 1:
            return True
 
        visited = [True]*length
 
        schedule = [0]
        visited[0] = False
        while schedule:
            cur_i = schedule.pop()
            for i in range(1, nums[cur_i]+1):
                if cur_i + i < length and visited[cur_i + i]:
                    # 방문 표시로 변경
                    visited[cur_i + i] = False
                    if (cur_i + i) == length -1 :
                        return True
                    schedule.append(cur_i + i)
        return False

파이썬 코드 - avail_index 활용

class Solution:
    def canJump(self, nums) -> bool:
        """
        Rumtime : faster than 71.24% of Python3
        Memory Usage : less than 5.28% of Python3
        """
        avail_idx = 0
        for cur_i in range(len(nums)):
            # 접근 불가능한 index임
            if cur_i != 0 and avail_idx < cur_i:
                return False
            avail_last_index = cur_i + nums[cur_i]
            # 최대 접근 가능한 index의 수치보다 큰 경우에는 avail_idx를 바꿔준다
            if avail_idx < avail_last_index:
                avail_idx = avail_last_index
 
            # 접근이 가능함
            if  (len(nums) -1) <= avail_last_index:
                return True
        return False