45. Jump Game II

45. Jump Game II

 

https://youtu.be/dJ7sWiOoK7g?si=bLV97rhs3OQMvktA

 

GPT: 그리디 알고리즘으로 해결

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        jumps = 0  # 최소 점프 횟수
        current_end = 0  # 현재 점프 범위 끝
        farthest = 0  # 현재 범위 내에서 도달 가능한 가장 먼 위치

        for i in range(n - 1):  # 마지막 위치는 탐색하지 않음
            # 현재 위치에서 도달 가능한 가장 먼 위치 갱신
            farthest = max(farthest, i + nums[i])

            # 현재 점프 범위 끝에 도달한 경우
            if i == current_end:
                jumps += 1  # 점프 횟수 증가
                current_end = farthest  # 점프 범위를 갱신

            # 이미 마지막 위치에 도달 가능한 경우 종료
            if current_end >= n - 1:
                break

        return jumps

 

왜 if current_end >= n - 1이 맞을까?

1. 도달 가능성을 확인:
   • current_end는 현재 점프 범위의 끝을 나타냅니다.
   • 만약 current_end가 n - 1보다 크거나 같다면, 현재 점프 범위 내에서 이미 마지막 위치(n - 1)에 도달 가능하다는 의미입니다.
   • 따라서 루프를 더 이상 돌 필요가 없습니다.
2. == 조건의 문제:
   • ==를 사용하면 정확히 current_end가 마지막 위치일 때만 종료됩니다.
   • 하지만, 점프의 범위는 >=일 수 있기 때문에 불필요하게 반복문이 계속 실행될 가능성이 생깁니다.

복잡도 분석

1. 시간 복잡도:
   • 배열을 한 번 순회 → O(n).
2. 공간 복잡도:
   • 추가 메모리 사용 없음 → O(1).

 

유투브

class Solution:
    def jump(self, nums: List[int]) -> int:
        res = 0  # 점프 횟수 초기화
        l = r = 0  # 초기 점프 구간 설정 (첫 번째 위치만 포함)

        # 현재 점프 구간 내에서 배열의 끝에 도달할 때까지 반복
        while r < len(nums) - 1:
            farthest = 0  # 현재 점프 구간에서 도달 가능한 가장 먼 위치
            
            # 현재 점프 구간 [l, r] 탐색
            for i in range(l, r + 1):
                farthest = max(farthest, i + nums[i])  # 가장 멀리 갈 수 있는 위치 갱신

            # 점프 구간을 다음으로 갱신
            l = r + 1  # 다음 점프 구간의 시작점
            r = farthest  # 다음 점프 구간의 끝점

            res += 1  # 점프 횟수 증가
        
        return res  # 최소 점프 횟수 반환

 

복잡도 분석

1. 시간 복잡도:
   • 내부 루프는 각 구간 내의 요소를 순회하며 최대 O(n)입니다.
   • 따라서 시간 복잡도는 O(n).
2. 공간 복잡도:
   • 추가 공간 사용 없이 상수 공간만 사용하므로 O(1).

 

GPT 코드가 더 이해가 잘 됨 !!