문제링크
https://leetcode.com/problems/jump-game-ii/?envType=study-plan-v2&envId=top-interview-150
📢 문제 간략설명
길이 n의 정수들로 이루어진 0-인덱스 배열이 주어집니다.
처음에 nums[0]에 위치합니다.
각 원소 nums[i]는 인덱스 i에서 앞으로 점프하는 최대 길이를 나타냅니다.
즉, nums[i]에 있으면 다음과 같은 경우 임의의 nums[i + j]로 점프할 수 있습니다.
- 0 < = j < = nums [ i ]
- i + j < n
최소 점프 횟수를 반환하여 nums[n - 1]에 도달합니다.
테스트 케이스는 nums[n - 1]에 도달할 수 있도록 생성됩니다.
입 출력 (1) :
Input: nums = [2,3,1,1,4]
Output: 2
입 출력 (2) :
Input: nums = [2,3,0,1,4]
Output: 2
📢 즉,
이 문제는 배열의 해당 인덱스의 값은 최대로 점프할 수 있는 값을 나타내며,
이 값 안에서 자유자재로 여러 인덱스에 옮겨 다니면서 마지막까지 도달하는 최소값을 출력하는 문제
📌풀이 알고리즘
1.배열의 끝에 도달하기 한칸 전까지 반복한다. 0~len(nums)-1
(맨 마지막 인덱스는 보지 않아도 전 단계에서 도착함을 알게됨)
2. 탐색 하는 인덱스의 값 만큼 점프한다.
3. 해당 값이 전에 점프한 값보다 큰지 비교하고 최대값을 뽑는다.
4. 인덱스 값을 증가하면서 max값을 찾는다.
5. 인덱스 값을 증가시켰는데, 전에 점프한 값 보다 작으면 그냥 지나감.
6. 점프한 값의 인덱스와 i값이 같을 때 다시 점프시작
📌소스코드 및 풀이방법
시간복잡도 : O(n)
class Solution:
def jump(self, nums: List[int]) -> int:
max_num = 0
max_jump = 0
jump = 0
for i in range(len(nums)-1):
max_num = max(max_num, i+nums[i])
if max_num >= len(nums)-1:
jump +=1
break
if i == max_jump:
jump+=1
max_jump = max_num
return jump
문제후기
머리가 진짜 안돌아감. ㅜㅜ 돌이 되었나.. 점프 해놓고 max값을 얻는데, i값을 증가시켰을 때 max값보다 작으면 어떻게 지나가지 한참 생각함 그냥 같을 때 jump 하는 조건 주면 되는거였음 머리가 굳었다 굳었어
> **참고**
https://youtu.be/hhVNvi_M-dA
