[Swift 알고리즘] LeetCode 922. Sort Array By Parity II

○ (투포인터 ×)

Two Pointers, Sorting | Medium

922. Sort Array By Parity II

문제
Given an array of integers nums, half of the integers in nums are odd, and the other half are even.
Sort the array so that whenever nums[i] is odd, i is odd, and whenever nums[i] is even, i is even.
Return any answer array that satisfies this condition.
Constraints
- 2 <= nums.length <= 2 * 10^4
- nums.length is even.
- Half of the integers in nums are even.
- 0 <= nums[i] <= 1000

1. O(2n)

아주 단순하고 직관적으로 배열을 추가로 생성해줘서 넣은 후, 차례대로 넣어주는 방법이다.

class Solution {
    func sortArrayByParityII(_ nums: [Int]) -> [Int] {
        var even = [Int]()
        var odd = [Int]()

        for num in nums {
            if num % 2 == 0 {
                even.append(num)
            } else {
                odd.append(num)
            }
        }

        var result = [Int]()
        for i in 0..<even.count {
            result.append(even[i])
            result.append(odd[i])
        }

        return result
    }
}

result 배열을 Array(repeating: 0, count: nums.count) 이렇게 먼저 생성해준 후,

다음과 같이 popLast() 혹은 removeLast() 의 반환값을 넣어주어 메모리에서 불필요한 배열을 바로 없애주는 방법도 있다. 

result[index] = evenNums.popLast() ?? 0

 

2. 투 포인터 사용 O(n)

짝수 홀수 배열을 추가로 생성해주지 않고, index를 2씩 더해주며 값을 넣어주는 방식이다. 

공간복잡도, 시간복잡도 측면에서 모두 이득인 것 같다. 

func sortArrayByParityII(_ nums: [Int]) -> [Int] {
    var result = Array(repeating:0, count:nums.count)
    var even = 0
    var odd = 1
    
    for num in nums{
        if num % 2 == 0{
            result[even] = num
            even += 2
        } else {
            result[odd] = num
            odd += 2
        }
    }
    return result
}