🏷️55. Jump Game
1. 문제 설명
-
당신은 정수 배열 nums를 받습니다. 초기 위치는 배열의 첫 번째 인덱스에 있으며, 배열의 각 요소는 해당 위치에서의 최대 점프 길이를 나타냅니다.
-
마지막 인덱스에 도달할 수 있는 경우 true를 반환하고, 그렇지 않으면 false를 반환하세요.
예시 1:
입력: nums = [2,3,1,1,4]
출력: true
설명: 인덱스 0에서 1로 1단계 점프한 다음 마지막 인덱스로 3단계 점프합니다.예시 2:
입력: nums = [3,2,1,0,4]
출력: false
설명: 무슨 일이 있어도 항상 인덱스 3에 도달합니다. 최대 점프 길이는 0이므로 마지막 인덱스에 도달할 수 없습니다.제약:
- 1 <= nums.length <= 10^4
- 0 <= nums[i] <= 10^5
2. 접근 방법
- 그리디 방식으로 접근하는데 여러 에러가 생겨 방식을 바꾸어 DP방식으로 접근해 보았습니다.
3. 구현 코드
👉 DP
class Solution {
public boolean canJump(int[] nums) {
int len = nums.length;
boolean[] dp = new boolean[len];
dp[0] = true; // 시작점은 항상 점프 가능
for(int i = 0; i < len; i++)
if(dp[i])
for(int j = 1; j <= nums[i]; j++){
if(i + j < len)
dp[i + j] = true;
}
return dp[len - 1];
}
}- 시간 복잡도: O(n^2)
- 공간 복잡도: O(n)
4. 개선 사항
class Solution {
public boolean canJump(int[] nums) {
int len = nums.length;
boolean[] dp = new boolean[len];
dp[0] = true; // 시작점은 항상 점프 가능
for(int i = 0; i < len; i++)
if(dp[i])
for(int j = 1; j <= nums[i] && i + j < len; j++)
dp[i + j] = true;
return dp[len - 1];
}
}- for 루프에 조건을 하나 더 추가
class Solution {
public boolean canJump(int[] nums) {
int reach=0;
for(int i=0;i<nums.length;i++){
if(reach<i){
return false;
}
reach=Math.max(reach,i+nums[i]);
}
return true;
}
}- DP 사용 없이 문제를 해결할 수 있는 방법
5. 최종 회고
- 처음 그리디 방식으로 접근하여 기본 예제를 통과하였지만 다른 testcase에서 계속 문제가 발생하였습니다. 그래서 새로운 접근 방법을 모색하다 DP방식으로 접근하였습니다. DP로 문제를 접근하니 보다 쉽게 코드를 작성하고 금방 해결할 수 있었습니다.
- 항상 씨드 생각이 중요한 것 같습니다. 지금은 시간에 여유를 두고 풀 수 있지만 코딩 테스트에서는 빠르게 다양한 방법을 생각하고 정확도를 생각해 보아야겠습니다.
