941. Sort Array By Parity

특별한 알고리즘 없이 구현하면 되는 쉬운 문제입니다.

방법은 많지만 선형 시간은 보장하는 것이 좋습니다. 공간 복잡도는 상수 공간(in-place)이든 선형 공간이든 각자의 선택인 것 같네요.

저는 직관적이고 내장 라이브러리에 존재하는 deque로 풀었습니다. 코드가 간결하고 가독성이 높습니다.

그 외에 고려해볼 방법이 몇 가지 있습니다.

배열 또는 리스트를 홀/짝 각각 만들고 나중에 합치기
배열을 하나 만들어 양끝부터 채우기
in-place, selection 알고리즘 앞에서부터 보다가 홀수를 찾으면 저장 뒤에서부터 보다가 짝수를 찾으면 그 위치에 저장된 홀수로 덮어씌우고 찾은 짝수를 저장 앞에서부터 보다가 홀수를 찾으면 그 위치에 저장된 짝수로 덮어씌우고 찾은 홀수를 저장 다 될 때까지 무한반복

Given an integer array nums, move all the even integers at the beginning of the array followed by all the odd integers.

Return any array that satisfies this condition.

Example 1:

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

Example 2:

Input: nums = [0]
Output: [0]

Constraints: