[Java Script]LeetCode 55. Jump Game

1. 문제 개요

문제 링크 : 55. Jump Game

Jump Game - LeetCode

• 주어진 배열의 각 원자는 배열에서 이동할 수 있는 최대 점프 값을 의미한다 
• 해당 배열이 배열의 끝에 도달할 수 있는지 확인하는 코드를 구현해라 

2. 문제 풀이

어떤 장소에서 점프를 하는 것이 가장 효율적인 선택이지 고민이 많았습니다.

저는 이부분을 각 위치에서 에서 점프할 때 가장 멀리 가는(선택지가 많은) 값을 효율적이라고 판단해 해당 부분을 찾아내고 적용하는 방식으로 코드를 구현하였습니다

 

이를 구현하기 위해 주석으로 코드의 구조를 잡아보면 다음과 같은데

var canJump = function(nums) {
    // 뛸 필요가 없는 경우 확인 (배열의 길이가 1)
	// 현재의 자리에서 점프해서 갈 수 있는 범위의 값이 다음 점프 값보다 멀리 갈수있는지 비교 
	// 효율적인 값이 생겼다면 점프 위치 변경
    // 현재의 점프로 끝지점에 도달할수 있다면 종료
};

 

LeetCode 요구 양식으로 코드 구현

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
    let jumpgage = 0, jumpPosition = 0;
    if(nums.length == 1){ return true }
    else{
        for(i = 0; i < nums.length; i++){
            if(jumpgage + jumpPosition < i) return false
            if(jumpgage + jumpPosition >= nums.length -1) return true
            if(i + nums[i] > jumpgage + jumpPosition){
                jumpPosition = i
                jumpgage = nums[i] 
            } 
        }
        return false
    }
};

 

LeetCode 제출 결과

 

이렇게 구현에 성공하였습니다.

 

3. 시간 복잡도 계산

splice와시간 복잡도의 적용입니다

O(n) = O(n)

 

4. 개선 사항 및 어려웠던 점

점프의 요건을 정하는것이 가장 어려웠던 문제 입니다. 사이의 있는 값을 모두 비교해야 했기에 더욱 그러했습니다.

 

5. 깃허브

관련 사항은 깃허브에 모두 기재되어 있습니다.