[LeetCode] 922. Sort Array By Parity II

문제 출처: https://leetcode.com/problems/sort-array-by-parity-ii/

Sort Array By Parity II - LeetCode

---

문제

홀수와 짝수 정수가 절반씩 구성된 정수 배열 nums가 주어진다.

 

i가 홀수일 때 nums[i]가 홀수가 되고, i가 짝수일 때 nums[i]가 짝수가 되도록 정렬하라.

 

이 조건을 만족하는 배열 중 하나를 반환하라.

예제

Input: nums = [4,2,5,7]
Output: [4,5,2,7]

Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.

Input: nums = [2,3]
Output: [2,3]

---

풀이

홀수 인덱스에 홀수 값이, 짝수 인덱스에 짝수 값이 있도록 하기 위해서, 제대로 정렬되어 있지 않은 원소들을 찾고 그 위치를 바꿔주는 것으로 문제를 해결할 수 있습니다.

 

다음과 같이 한 번의 교환으로 두 개의 값이 제자리를 찾아가는 것을 볼 수 있습니다.

var sortArrayByParityII = function(nums) {
    let odd = 1, even = 0;
    while (odd < nums.length && even <nums.length) {
        while (odd < nums.length && nums[odd] % 2 == 1) { odd += 2; }
        while (even <nums.length && nums[even] % 2 == 0) { even += 2; }
        
        if (even < nums.length && odd < nums.length) {
            [nums[odd], nums[even]] = [nums[even], nums[odd]];
        }
    }
    return nums;
};

1. 홀수 인덱스를 탐색할 odd와 짝수 인덱스를 탐색할 even을 선언
2. 이 두 값을 활용하여 홀수 인덱스인데 짝수 값이 있거나, 짝수 인덱스인데 홀수 값이 있는 위치를 탐색
3. 두 변수(odd와 even)가 가리키고 있는 위치의 값을 교환
4. 과정 2~3을 odd 또는 even이 탐색 범위를 벗어날 때까지 반복

시간 복잡도는 odd와 even이 각각 배열의 절반을 탐색하므로 $O(n)$이 됩니다.

 

Github: https://github.com/opwe37/Algorithm-Study/blob/master/LeetCode/src/922.js

GitHub - opwe37/Algorithm-Study