1.문제
Jump Game - LeetCode
Can you solve this real interview question? Jump Game - You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position. Return true if you can
leetcode.com
2.문제설명
주어진 배열에서 배열의 요소로 마지막 인덱스 까지 갈 수 있는지 판단하는 문제이다.
3.소스코드
class Solution {
public boolean canJump(int[] nums) {
int curr = 0;
int lastIdx = nums.length - 1;
for (int i = 0; i <lastIdx; i++) {
if(curr < i ){
return false;
}
if (nums[i] == 0 && curr == i) {
return false;
}
int maxJmp = i + nums[i];
if(maxJmp > curr){
curr = maxJmp;
}
if(curr >= lastIdx){
return true;
}
}
return true;
}
}4.코드 해설
현재 위치를 판단할 cuur 변수와 최대 배열의 길이까지 선언을 한다.
반복 문을 통해 마지막 인덱스까지 도착을 할 수 있는지 반복을 하면서 현재 최대 위치(curr) 이 i 현재 위치 보다 넘어서면 불가능 하므로 False를 반환한다.
nums[i] 가 0 일경우에는 점프를 할 수 없고 현재 최대 위치(curr)이 현재 위치이면 점프를 할 수 없는 상황이 므로 false를 반환한다.
중요한 점프 방법은 maxJum = 현재위치 + nums[i] (점프 할수 있는 값) 을 저장해 최대 점프를 구한다.
최대 점프 할 수있는 (curr)이 마지막 보다 크면 마지막 인덱스 까지 갈 수 있으므로 true 를 반환하다.
5. 회고
다른 사람들의 소스 코드
class Solution {
public boolean canJump(int[] nums) {
int i = 0;
for (int reach = 0; i < nums.length && i <= reach; ++i)
reach = Math.max(reach, i + nums[i]);
return i == nums.length;
}
}
접근 방식은 비슷 하지만 코드가 훨씬 간결 하다. for문에서 예외처리를 하되 메서드를 잘 활용한다면 최대점프 구간을 간결하게 구할 수 있다.
메서드의 활용을 한다면 좀더 간결하게 구현 할 수 있는문제였던 것 같다.