.leetcode(905. Sort Array By Parity)

https://leetcode.com/problems/sort-array-by-parity/

 

1. 2022/04/25 시도

소요시간: 5분

class Solution {
    public int[] sortArrayByParity(int[] nums) {
        
        int lastEvenIndex = -1;
        for (int i=0; i<nums.length; i++) {
            if (nums[i] % 2 == 0) {
                swap(nums, i, ++lastEvenIndex);
            }
        }
        
        return nums;
    }
    
    private void swap(int[] nums, int p, int q) {
        if (p == q) {
            return;
        }

        int temp = nums[p];
        nums[p] = nums[q];
        nums[q] = temp;
    } 
}

풀이 접근 과정

마지막 짝수 인덱스를 기억하는 방식이다.
처음에는 없으니 -1로 세팅한다.
그 대신 짝수인덱스 다음 세팅하기 전에 ++를 해준다.

swap은 간단하게 함수를 구현하였다.
동작은 짝수를 찾으면 짝수 인덱스로 swap해주는 것이다.

 

느낀점

• O(n)의 시간복잡도로 간단하고 깔끔하게 잘 풀었다. 전체적인 시간도 많이 안 걸렸다.
• https://silvergoni.tistory.com/entry/leetcode-283-Move-Zeroes에서 swap방식으로 솔루션이 소개되었는데 그 방식으로 풀어보았다. 
• 다른 사람들 풀이를 보다가 two-pointer로 푸는 방식이 있어서 재미나서 소개한다. 흔히 배열문제를 풀때, left-right-while접근방식이 있다고 생각하는데 그 방법으로 푼 것이다.

class Solution {
    public int[] sortArrayByParity(int[] nums) {
        int left = 0; 
        int right = nums.length-1;
        
        while (left < right) {
            if (nums[left] % 2 == 0) {
                left++;
                continue;
            }    
            
            if (nums[right] % 2 == 1) {
                right--;
                continue;
            }
            
            swap(nums, left, right);
        }

        return nums;
    }
    
    private void swap(int[] nums, int p, int q) {
        if (p == q) {
            return;
        }

        int temp = nums[p];
        nums[p] = nums[q];
        nums[q] = temp;
    } 
}

 

---

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

반응형