solution
/**
* @param {number[]} nums
* @return {boolean}
*/
var canJump = function(nums) {
// nums의 길이가 1인 경우.
// nums[0]가 0이더라도, 이미 마지막 인덱스이기 때문에 상관없게 됨.
if(nums.length === 1){
return true;
}
// nums의 길이가 2 이상인 경우.
// nums[0]가 0이면 움직일 수 없음.
if(nums[0] === 0){
return false;
}
let index = 0;
let move = 0;
while(index < nums.length){
move = Math.max(move, index + nums[index]);
if(move >= nums.length - 1){
return true;
}
if(nums[index] === 0 && index >= move){
return false;
}
index++;
}
return false;
};
이번 문제는 사실 알고리즘 사고를 적용했다기 보다는, 될 때까지 돌려보면서 예외 처리를 변경해나갔다.
방법은 다음과 같다.
현재 인덱스에서 이동할 수 있는 최대 거리를 구한다.
만약, 그 거리가 마지막 인덱스보다 크다면 그대로 true이다.
여기까지는 매우 간단하다.
그런데 그렇지 않은 경우에 대해서 처리를 잘 해주지 않으면 미세한 차이로 계속 정답을 틀리게 된다.
만약 마지막 인덱스까지 도달하지 못하는 경우에는 두 가지를 체크한다.
- 현재 인덱스의 값이
0인지를 체크한다. - 현재 인덱스가 움직일 수 있는 최대 거리보다 같거나 큰지 체크한다.
필자는 1번 조건만 생각하다가 많은 오답을 겪게 되었다.
1번 조건만 생각하는 경우 다음의 문제가 발생한다.
문제에서 주어진 테스트 케이스 중 하나를 예시로 보자.
nums = [3,0,8,2,0,0,1]
loop 1) index === 0, move === 3, [다음 index로 이동]
loop 2) index === 1, move === 3, nums[1] === 0, [return false]1번 조건만 생각한다면 이 때 false가 된다.
그러나, 배열을 잘 보면 전혀 그런 상황이 아니다.
0번 인덱스에서 2번 인덱스로 넘어가면 true가 될 수 있기 때문이다.
즉, 현재 인덱스의 값이 0이 되더라도, 추가적인 조건을 판단해야한다는 것이다.
그게 뭘까? 더 이상 나아갈 수 없다고 판단할 수 있는 조건이 뭐가 더 있을까?
바로, 현재 인덱스가 움직일 수 있는 최대 거리(move)보다 같거나 큰 경우이다.
위 예시에서 false 처리가 바로 안된다고 가정하고,
다음 루프로 들어가보자.
loop 3) index === 2, move === 10, nums[2] === 8그리고 또 다른 테스트 케이스에 대해서 살펴보자.
nums = [3,2,1,0,4]
loop 1) index === 0, move === 3, [다음 index로 이동]
loop 2) index === 1, move === 3, nums[1] === 2, [다음 index로 이동]
loop 3) index === 2, move === 3, nums[2] === 1, [다음 index로 이동]
loop 4) index === 3, move === 3, nums[3] === 0, [return false]첫 번째 예시는 0이 나왔다고 해서 바로 false를 하면 안됐지만,
두 번째 예시는 0이 나왔을 때 바로 false를 했고, 이는 정답이었다.
둘의 차이를 보면 2번 조건의 이유를 알 수 있을 것이다.
index >= move인 상황에서만 확실하게 false를 말할 수 있는 것이다.
move는 지금까지 점프할 수 있는 최대치를 사용해 온 값과
현재 인덱스에서 최대로 점프했을 때의 값 중 더 큰 것을 사용한다.
첫 번째 예시의 경우 index < move이기 때문에 다음 인덱스에서 어떤 일이 일어날지 모르는 상황이다.
최대로 갈 수 있는 거리(move)가 현재 거리(index)보다 길기 때문이다.
실제로, 8이 다음 인덱스에 있었으므로 0인 값을 넘어갈 수만 있다면 앞으로 나아갈 수 있었다.
두 번째 예시의 경우 index > move이기 때문에 다음 인덱스를 보지 않아도 이미 앞으로 갈 수가 없는 상황이다.
첫 번째 예시의 경우와 반대되는 상황인 것이다.
최대로 갈 수 있는 거리(move)가 현재 거리(index)보다 작기 때문에 더 이상 가도 의미가 없는 것이다.
같은 경우에도 마찬가지이다. 제자리 걸음이 되기 때문에.
다른 분의 solution
/**
* @param {number[]} nums
* @return {boolean}
*/
var canJump = function(nums) {
let idx = 0;
let max = 0;
let target = nums.length - 1;
while(idx < nums.length) {
max = Math.max(max, idx + nums[idx]);
if (max >= target) {
return true;
}
if (max <= idx && nums[idx] === 0) {
return false;
}
idx++;
}
return false;
};다른 분도 같은 로직을 사용하셨다. 그런데 이 분은 사용한 알고리즘이 명확하게 표시되어 있었다.
greedy 알고리즘을 사용하셨다고 한다.
그리디 알고리즘은 탐욕 알고리즘 또는 욕심쟁이 알고리즘이라고도 불리는데요. 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법입니다. 이렇게 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘이죠.
- 제로초님 게시글 -
아마 이러한 이유로 greedy 알고리즘을 사용한 것 같다.
그러나...greedy 알고리즘이 적용되기 좋은 문제인지는 솔직히 모르겠다.
필자는 거의 때려맞추다싶이 해결했기 때문에 할 말이 없지만,
greedy 알고리즘은 현재의 선택이 다음의 선택에 영향을 주면 안된다고 알고 있기 때문이다.
이 문제는 현재의 선택이 다음의 선택에 꽤나 영향을 주는 문제라고 생각한다.
물론, 문제를 바라보는 관점에 따라 전혀 그렇지 않을 수도 있다.
