[LeetCode] 905번 - Sort Array By Parity(홀짝성 여부로 배열 정렬)

문제

905. Sort Array By Parity

Easy

Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.

You may return any answer array that satisfies this condition.

 

Example 1:

Input: [3,1,2,4]
Output: [2,4,3,1]
The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

 

Note:

1. 1 <= A.length <= 5000
2. 0 <= A[i] <= 5000

풀이과정

(1) 규칙

오름차순,내림차순 상관없이 짝수를 전부 앞에 배치하도록 합니다.

단,

1 <= A.length <= 5000

0 <= A[i] <= 5000

이라는 조건을 고려하여 최대한 연산횟수가 적도록 구현합니다.

(2) 순서

swap()을 이용하거나

짝수들만 다른 버퍼에 넣은후, 홀수만 남은 원배열과 합해서 출력하는 방법을 사용합니다.

또는 for문을 돌면서 새 버퍼에 짝수는 맨앞, 홀수는 맨뒤에다가 추가해줍니다.

(3) 코드

C++

#include <iostream>
#include <vector>
using namespace std;
 
vector<int> sortArrayByParity(vector<int>& A) {
    vector<int> answer;
    
    for (vector<int>::iterator it = A.begin();
        it != A.end(); )
    {
        if (*it % 2 == 0)//짝수
        {
            answer.push_back(*it);
            it = A.erase(it);
        }
        else it++;
    }
    answer.insert(answer.end(), A.begin(), A.end());
    return answer;
}

Python

(1) 런타임 속도 제일 빠름

class Solution:
    def sortArrayByParity(self, A):
        odd=[]
        even=[]
        for i in range(len(A)):
            if A[i]%2==0:
                even.append(A[i])
            else:
                odd.append(A[i])
        return even+odd

(2)

class Solution:
    def sortArrayByParity(self, A):
        answer=[]
        for i in range(len(A)):
            if A[i]%2==0:
                answer.insert(0,A[i])
            else:
                answer.append(A[i])
        return answer

(3)

class Solution:
    def sortArrayByParity(self, A):
        answer = collections.deque()
        for i in range(len(A)):
            answer.appendleft(A[i]) if (A[i]%2==0) else answer.append(A[i])
        return answer