[LeetCode] 55. Jump Game

https://leetcode.com/problems/jump-game/description/

Jump Game - LeetCode

문제 유형 : 배열

문제 난이도 : Medium

 

문제

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 reach the last index, or false otherwise.

 

정수 배열 nums가 주어집니다. 배열의 첫 번째 자리부터 시작하고, 자리의 숫자는 그 자리에서 최대 점프할 수 있는 거리입니다.

 

마지막까지 도착할 수 있으면 true를, 아니면 false를 반환하시오.

 

풀이

1. 0을 발견한 다음, 뛰어넘을 수 있는 0인지 찾는 방법

 

거꾸로 배열 탐색을 시작한다(n-1 인덱스부터 시작). 탐색하다 0을 만나면 0의 위치를 새로운 배열 zeros에 추가한다.

0이 아니라면, 새로운 배열 zeros에 있는 위치들을 넘을 수 있는지 확인한다. 넘을 수 있으면 zeros에 있는 그 위치를 지운다.

다 돌고 나서도 배열 zeros가 남아있다면 false를, 비어있다면 true를 반환시킨다.

 

2. 최대 거리와 비교하기

 

처음부터 탐색을 시작한다. 

탐색을 하면서 점프로 최대한 갈 수 있는 위치를 매번 갱신한다.

만약 갈 수 있는 최대 인덱스보다 탐색하는 위치가 더 커지면, false를 반환하고, 무사히 탐색이 끝나면 true를 반환시킨다.

 

 

코드(C++)

1. 0을 찾아서 비교하기

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int idx = n-2;
        vector<int> zeros;
        while(idx >= 0){
            if(nums[idx] == 0){
                zeros.push_back(idx);
            }
            else{
                for(int i = 0; i < zeros.size(); i++){
                    if(nums[idx] + idx > zeros[i]){
                        zeros[i] = -1;
                    }
                }
                zeros.erase(remove(zeros.begin(), zeros.end(), -1), zeros.end());
            }
            idx--;
        }
        return zeros.empty();
    }
};

 

 

2. 최대 이동가능위치와 비교하기

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int reach =0;
        for(int i=0 ; i< nums.size(); i++){
            if(i>reach) return false;
            reach = max(reach, i+nums[i]);
        }
    return true;
    }
};