LeetCode 55. Jump Game

심규환·2022년 4월 19일
0

Algorithm

목록 보기
3/5

문제 링크 :https://leetcode.com/problems/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 reach the last index, or false otherwise.

설명 : nums에 들어있는 값은 최대로 점프 뛸 수 있는 거리이다. 만약 nums =[3,2,1,0,4] 이면, 제일 처음 index = 0 부터 시작하게 된다.
nums[0] 은 '3'이니 오른쪽으로 3칸까지 이동할 수 있다. 그러면 index= 0(현 위치) + 3가 되고, nums[3] = 0 이다. 더 이상 점프를 뛸 수 없기 때문에 이는 실패를 리턴하게 된다.

만약 nums = [0] 이면 첫 시작부터 제일 마지막 인덱스이기 때문에 이는 성공하게 된다.

코드

class Solution {
bool isZero(vector &v, int start){
if(find(v.begin()+ start, v.end(), 0) == v.end()) return false;
return true;
}

public:
bool canJump(vector& nums) {
if(!isZero(nums, 0)) return true;
int lastIdx = nums.size()-1;

      vector<int> visit;
      visit.assign(nums.size(), 0);

      visit[0] = 1;

      for(int i=0; i<nums.size(); i++){
          if(visit[lastIdx]==1) return true;
          if(visit[i] == 1){
              int tmp = i+1;
              for(int j=0; j<nums[i]; j++){
                  // overflow 
                  if(tmp > lastIdx)break;

                  visit[tmp] = 1;
                  tmp++;
              }
          }
      }	

      return false;	
  }
};


코드 설명 :
제일 먼저 isZero 함수를 통해서 만약 배열 안에 0 값이 없다면 바로 true를 리턴한다.

nums = [2,3,0,0,2,0] 이라고 해보자.
갈 수 있는지 여부를 확인할 수 있는 t = [0,0,0,0,0,0] 를 추가로 생성한 뒤, 제일 처음 값은 갈 수 있으니 1로 초기화 해준다.
visit = [1,0,0,0,0,0]
visit 배열에서 갈 수 있는 곳은 1로 표시한다.
nums 값을 하나씩 순회하면서 갈 수 있는 곳이고 nums[i] 값이 존재하면 nums[i] 만큼 visit 배열에 1로 변환해준다
ex) t[0] = 1 이고 nums[0] = 2 이니, 2 만큼 움직여서 visit[1] = 1, visit[2] = 1로 갈 수 있음을 표시한다. visit = [1,1,1,0,0,0]

순회 도중 제일 마지막 idx 값이 1이 되면 갈 수 있다는 것이므로 true를 반환하고 아니면 false를 반환한다.

profile
장생농씬가?

0개의 댓글