[1스4코2파] # 247. LeetCode 45. Jump Game II

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

Rule :

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

START :

[3코1파] 2023.01.04~ (247일차)
[4코1파] 2023.01.13~ (240일차)
[1스4코1파] 2023.04.12~ (151일차)
[1스4코2파] 2023.05.03 ~ (129일차)

Today :

2023.09.07 [247일차]
45. Jump Game II
https://leetcode.com/problems/jump-game-ii/

45. Jump Game II

문제 설명

정수로 주어진 배열 nums의 각 인덱스의 원소는 본인의 인덱스에서 이동할 수 있는 최대 거리를 의미하는데, 주어진 배열에서 마지막 인덱스에 도달 가능한 최소 이동 횟수를 구하는 문제임

문제 풀이 방법

greedy 알고리즘으로 O(n)으로 풀 수 있는데,
주어진

내 코드

 class Solution:
    def jump(self, nums: List[int]) -> int:
        res = 0
        l = r = 0
        while r < len(nums) -1:
            farthest = 0
            for i in range(l, r+1):
                farthest = max(farthest, i+nums[i])
            l = r+1
            r = farthest
            res +=1 
        return res           

증빙

여담