Leetcode[day24] - Jump Game

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Note:
1. You must do this in-place without making a copy of the array.Minimize the total number of operations.
2. Minimize the total number of operations.

Input: nums = [3,2,1,0,4]

Output: false 

Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

1. 알고리즘을 해결하기 위해서 생각한 방법

 

 - 해당 문제는 배열 nums가 주어질 때, nums[i]의 값만큼 현재 i에서 뛸 수 있다. 그럴 때, nums.length-1에 도달할 수 있는가에 대한 문제이다.

 - 어려웠던 점은 왜인지 모르게, 4까지 도달하지 못 했다.

 

2. 알고리즘 작성 중, 어려운 점

 

 - nums의 마지막에 도달하는 것에 치중해서 문제를 풀다보니 마지막에 도달하지 못 했다.

 - 특히, i와 nums[i]를 통해서 특정 값에 도달해야 해서, 계속 헷갈렸다.

 - 그래서 영상을 통해서 학습을 했다.  

 

3. 다른 사람이 작성한 알고리즘

 

https://www.youtube.com/watch?v=oZPXQ7igs6s&t=214s

 

4. 다른 사람이 작성한 알고리즘을 보고 배운 점

 

- i + nums[i]를 통해서 어디까지 점프할 수 있는 지 알 수 있다.

- maxIndex = Math.max(max, i + nums[i])를 이용해서, 0이면 자기 자신을 가리킬 수 있게 된다.

- if(maxIndex==i && nums[i] == 0), maxIndex가 자기 자신을 가리키고, nums[i]인 점프력이 0이라면 앞으로 가지 못 한다는 조건으로, 도달하기 위한 조건이 아닌, 아닌 조건을 빼서 마지막에 도달하지 못 할 때만, false를 한다.

 

 

5. 다른 사람이 작성한 알고리즘을 보고 배운점

 

 - 참인 조건을 생각하기 보다는, 아닌 조건을 걸러서 참인 조건에 도달할 수 있다면, 그게 더 효율적일 수 있다.

 - A = Math.max(A,B) 와 같이 A와 B의 조건을 가르는 케이스를 충분히 생각해보자.

 

6. 결과

 

 

문제 : https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/531/week-4/3310/

Account Login - LeetCode