.leetcode(283. Move Zeroes)

https://leetcode.com/problems/move-zeroes/

 

2. 2022/04/25 시도

소요시간: 8분

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

            nums[pos++] = nums[i];
        }
        
        for (int i=nums.length-zeros; i<nums.length; i++) {
            nums[i] = 0;
        }
    }
}

풀이 접근 과정

먼저 pos를 선언해서 0이 아닌 숫자의 인덱스를 세팅한다.
그래서 zeros로 0의 갯수를 센다.

마지막에 0의 갯수만큼 nums 배열을 0으로 대입해준다.

 

느낀점

• O(n)의 시간복잡도로 풀었다. 깔끔한 문제다.
• 예전 풀이를 보니 확실히 실력이 나아졌다. 예전에는 O(n^2)으로 풀었다. 이번에는 솔루션에서도 권장하는 2번방식으로 풀었다.
• swap을 하는 방식도 있는데 괜찮은 방식이지만 지금의 방식이 더 좋다.

 

---

1. 2021/01/02 시도

소요시간: 17분

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

풀이 접근 과정

O(n)걸리겠다.생각해보니 N^2이 걸릴거 같다.
숫자와 0을 swap해주면 되겠다.

 

느낀점

• 문제를 잘 읽어야된다. 소팅까지 해야하는지 알고 처음에 잘 못 풀었다. 상대적 순서만 유지하면되었는데 desc를 만족하도록 구현했다.
• 원리는 마지막 0의 위치를 기억해두면서 0을 발겨할때마다 한칸씩 시프트해주는 방식이다. 이것도 최적의 방식은 아니다.
• 솔루션보다가 갑자기 떠올랐는데 0의 갯수만 세고 0의 갯수가 늘어날때마다 인덱스에 반영해서 땡겨준 다음 마지막에 0을 갯수만큼 붙여줘도 되겠다. 마침보니 솔루션 2도 거의 비슷한 방식으로 되어있다. 정렬을 해야한다고 생각해서 처음부터 이 생각을 하진 못했다.
• 솔루션3번은 0을 몰고 가는 swap하는 방식인데 꽤나 흥미롭다.

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형