LeetCode - Jump Game I
문제 설명
해당 문제는 배열 nums가 주어질 때, nums[i]의 값만큼 현재 i에서 점프를 뛸 수 있다.
위와 같은 상황에서, nums.length-1에 도달할 수 있는가에 대한 문제이다.
도달할 수 있다면 true를 반환하고 아니라면 false를 반환해야 한다.
입력 예시는 다음과 같다.
solution([2, 3, 1, 1, 4]); // true
solution([3, 2, 1, 0, 4]); // false
소스 코드
function solution(arr) {
let last = arr.length - 1;
// 배열의 마지막 인덱스부터 루프를 돈다.
for (let i = last; i >= 0; i--) {
// 4 ... last === 4
// 3 ... 3 + 1 >= last(4) ? last = 3
// 2 ... 2 + 1 >= last(3) ? last = 2
// 1 ... 1 + 2 >= last(2) ? last = 1
// 0 ... 0 + 2 >= last(1) ? last = 0
if (i + arr[i] >= last) {
// if문의 조건이 참일시, last를 매번 최신화시켜준다.
// i + arr[i] 가 last 보다 크거나 같다면, arr[i]는 last에 점프가 가능한(도달할 수 있는) 것이다.
// 즉 i + nums[i]를 통해서 어디까지 점프할 수 있는 지 알 수 있다.
last = i;
};
};
// last 값이 0 이라면 배열의 last element까지 점프가 가능한 것이므로 true를 반환한다.
return last === 0 ? true : false;
}
solution([2, 3, 1, 1, 4]); // true
// solution([3, 2, 1, 0, 4]); // false
위 소스 코드의 시간복잡도는 O(n) 이다.
유튜브에 Jump Game의 요구사항에 대해 상세한 설명을 해주는 영상이 있어서
이를 참고하여 문제의 의도를 정확히 이해할 수 있었다.
영상 링크는 다음과 같다.
Youtube | Jump Game
Author And Source
이 문제에 관하여(LeetCode - Jump Game I), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@alsghk9701/LeetCode-Jump-Game저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)