[leetcode #922] Sort Array By Parity II

Problem

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.

Example 1:

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.

Example 2:

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

Constraints:

・ 2 <= nums.length <= 2 * 10⁴
・ nums.length is even.
・ Half of the integers in nums are even.
・ 0 <= nums[i] <= 1000

Idea

아주 쉬운 문제가 나왔다. 이렇게 쉬운 문제가 나오면 문제를 푸는 것보다 얼마나 더 효율적으로 문제를 풀 수 있을지 고민해봐야 한다. 정답으로 리턴할 array를 새로 생성할 것인지, 기존의 array 값을 바꿔 리턴할 것인지 등을 고려하여 다양한 답을 낼 수 있다.

가장 효율적인 방법은 홀수와 짝수 head를 각각 둬서, index에 맞지 않는 값일 경우 head를 서로 맞바꾸는 것이다.

나는 직관적으로 문제를 빨리 풀었는데, 조건에 맞지 않는 값과 index를 따로 list로 관리하였다. 이후 list를 탐색하면서 각 값을 맞바꾸어 준다.

알고리즘은 다음과 같다.

1. 주어진 array를 탐색하면서 짝수인 index에 홀수가 들어있거나, 홀수인 index에 짝수가 들어있다면 값과 index를 각 list에 넣어준다.
2. 생성한 list를 탐색하면서 홀수와 짝수를 서로 맞바꿔준다.
3. 값을 바꾼 array를 그대로 리턴한다.

Solution

class Solution {
    public int[] sortArrayByParityII(int[] nums) {
    	List<Integer> odds = new ArrayList<>();
        List<Integer> evens = new ArrayList<>();
	List<Integer> oddIndexes = new ArrayList<>();
        List<Integer> evenIndexes = new ArrayList<>();

        for (int i=0; i < nums.length; i++) {
            if (i % 2 == 0 && nums[i] % 2 == 1) {
                odds.add(nums[i]);
                oddIndexes.add(i);
            }
            if (i % 2 == 1 && nums[i] % 2 == 0) {
                evens.add(nums[i]);
                evenIndexes.add(i);
            }
        }

        for (int i=0; i < odds.size(); i++) {
            int odd = odds.get(i);
            int even = evens.get(i);
            int oddIndex = oddIndexes.get(i);
            int evenIndex = evenIndexes.get(i);
            nums[evenIndex] = odd;
            nums[oddIndex] = even;
        }

        return nums;
    }
}

Reference

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