LeetCode - Jump Game 2
문제 설명
자연수 배열이 주어진다. 배열의 첫 인덱스 부터 시작해서 마지막 index까지 Jump를 해서 도착해야 한다.
각각의 배열의 원소가 가리키는 값은 그 자리에서 jump 할 수 있는 거리를 가리키며,
마지막 Index까지 도착했을때 최소의 jump 횟수를 찾아라 라는 것이 문제다.
해결방법
제일 먼저 떠오른 방법은 동적계획법이다.
참,, 난 Greedy 문제를 풀러왔는디,,
아무튼 어떻게 하면 풀 수 있을까 머리를 굴려보다가
jumps 배열을 생성하고
jumps[0] = 0 으로 설정하고 이중 포문을 설정해서 을 해두면
모든 배열에 대한 각각의 최소 jump 거리값을 구할 수 있다.
Code
import java.lang.*;
import java.util.*;
class Solution {
public int jump(int[] nums) {
int[] jumps = new int[nums.length];
Arrays.fill(jumps,Integer.MAX_VALUE);
jumps[0] = 0;
for(int i=0; i<jumps.length; i++){
for(int j=i+1; j<=i+nums[i]&&j<nums.length; j++){
jumps[j] = Math.min(jumps[i]+1,jumps[j]);
}
}
return jumps[nums.length-1];
}
}
소감
아무래도 모든 경로의 수를 구하다 보니 이 되버린다.
아마 방식의 시간복잡도가 있는 모양이다.
찾아보니 2 Pointer
를 이용해서 해결하는 방법이 있더라.
시간복잡도는 좀 줄여야 겠지만
예전에 비해 문제 푸는 속도가 매우 줄었다. 라고 합리화를 해본다...
Author And Source
이 문제에 관하여(LeetCode - Jump Game 2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ehdrms2034/LeetCode-Jump-Game-2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)