LeetCode[day4] - Move zeros

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.

Example:
Input: [0,1,0,3,12] Output: [1,3,12,0,0]

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

 

 - 문제의 조건에서는 별도의 다른 array 공간을 만들면 안 된다고 적혀있었다. 그래서 해당 문제를 해결하기 위해서 생각한 방법은 0인 숫자들을 뒤로 미루는 방법을 생각했다. 그래서, nums의 아이템들 중에서, 값이 0인 경우에 값을 뒤로는 로직을 생각했고, 이것을 input으로 받은 길이의 크기의 반만큼 실행해서, 옮겨줘야하는 point를 이동시켜줬다.

 

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

 

 - 문제를 풀고 나서, 오 괜찮게 풀지 않았을까 라고 생각을 했다. 굳이 어려운 점이 있었다면, 처음에는 for문을 1중으로만 돌려, 결과가 제대로 나오지 않는 것을 알게 되었고, 크기의 반만큼 돌려줘야 한다는 것을 생각하게 되었다.

 

3. 내가 작성한 알고리즘

 

class Solution {
    public void moveZeroes(int[] nums) {
        for(int i=0; i<nums.length/2+1 ;i++){
            for(int j=0; j<nums.length-1; j++){
            if(nums[j] == 0){
                int temp = nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = temp;
            }
         }
        }
    }
}

4. 내가 작성한 알고리즘 결과

쥰내 느리네.. 퍼센트에 나오지도 않네

 

5. 다른 사람이 작성한 알고리즘 보기

 

class Solution {
    public void moveZeroes(int[] nums) {
        int point = 0;
        for(int i=0; i<nums.length ;i++){
            if(nums[i] != 0){
                nums[point] = nums[i];
                point++;
            }
        }
        for(int i=point; i<nums.length; i++){
            nums[i] = 0;
        }
    }
}

 

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

 해당 로직을 생각한 사람은 point라는 변수를 두고, 0이 아닌 값이 나올 때, 해당 값을 배열에 넣는 방법을 생각했다. 이를 통해서, 가장 효율적으로 for문을 1바퀴만 돌려서 원하는 결과를 얻을 수 있었다.

 

7. 반성할 점

 - 버블소트에서 착안을 둔 아이디어는 역시 안 좋다.

 - point를 이용해서 해당 배열의 필요한 부분에 값을 넣는 알고리즘을 항상 생각하자.

 

8. 짝짝짝 결과

ㅋㅋㅋㅋㅋㅋㅋㅋㅋ대단하넴

 

문제 : https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/528/week-1/3286/

Explore - LeetCode