[LeetCode] 45번 Jump Game II 문제를 풀어보았다. (ft. java)

2023년 02월 08일 수요일 - T1!

오늘 올려볼 문제는 45번 Jump Game II 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

아 생각보다 잘 못 풀어서 아쉽

입력

사진에서도 볼 수 있듯이 int 배열 1개가 입력으로 들어온다.

---

풀이 및 코드

각 원소에 있는 수의 길이를 최대로 점프할 수 있다고 할 때 배열의 끝까지 가장 적은 점프로 갈 수 있는 점프수를 구하는 문제이다.

오늘은 처음부터 정답을 생각해냈다.

dp를 사용하고 count를 저장하는데 최대로 점프뛸 수 있는곳에 이미 저장한 값이 있으면 넘어가고 없다면 해당 길이까지 모두 dp를 채워가는 식으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        var arr = new int[n];
        
        if(n == 1) return 0;
        
        for(int i = 0; i < n; i++) {
            if(i + nums[i] >= n - 1) return arr[i] + 1;
            
            for(int j = i + 1; j <= i + nums[i]; j++) {
                if(arr[j] > arr[i] || arr[j] == 0) arr[j] = arr[i] + 1;
            }
        }
        
        return 0;
    }
}

---

제출 화면

discuss를 보니 훨씬 간단하면서 멋있고 섹시한 코드가 있었다.

이런 코드들을 잘 기억해두고 나중에 응요해봐야겠다.

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.