[1스4코2파] # 246. LeetCode 55. Jump Game

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (246일차)
[4코1파] 2023.01.13~ (239일차)
[1스4코1파] 2023.04.12~ (150일차)
[1스4코2파] 2023.05.03 ~ (128일차)

Today :

2023.09.06 [246일차]
55. Jump Game
https://leetcode.com/problems/jump-game/

55. Jump Game

문제 설명

정수 배열 nums가 제공됐을 때, 배열의 첫 번째 인덱스는 첫번째 위치이고, 배열의 각 요소는 해당 위치에서의 최대 점프 길이를 나타낼 때,
마지막 인덱스에 도달할 수 있으면 true를 반환하고 그렇지 않으면 false를 return함

문제 풀이 방법

DP를 이용해서 풀면 time limit이 나지 않는다.
마지막 인덱스까지에 도달을 보면 되는 문제라서, 마지막 인덱스로 부터 주어진 배열을 거꾸로 탐색한다.
도달해야 하는 goal을 배열의 맨 끝 원소로 두고,
"주어진 인덱스"와 "주어진 인덱스의 원소(최대 움직일 수 있는 길이)" 의 합이 goal보다 크거나 같으면 goal을 주어진 인덱스로 갱신하면서, 첫 배열까지 가는데 순회를 다했을 때, 갱신된 goal이 0이라면 True, 아니라면 False를 return 하는 방법으로 풀면 된다.

내 코드

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        goal = len(nums) -1

        for i in range(len(nums)-1, -1, -1):
            if i + nums[i] >= goal:
                goal = i
            
        return True if goal == 0 else False               

증빙

여담