JavaScript 특수 정렬 알고리즘: 짝수는 오름차순, 홀수는 내림차순으로 정렬하기

문제 개요

정수로 이루어진 배열을 유일한 인자로 받아, 아래 조건에 따라 정렬하는 JavaScript 함수를 작성해야 합니다.

모든 짝수는 오름차순(작은 수부터 큰 수 순서)으로 정렬합니다.
모든 홀수는 내림차순(큰 수부터 작은 수 순서)으로 정렬합니다.
짝수와 홀수의 상대적 위치는 원본 배열과 동일하게 유지합니다.

예시

입력 배열이 다음과 같다고 가정해 보겠습니다.

const arr = [12, 17, 15, 24, 1, 6];

이때 기대되는 출력은 다음과 같습니다.

const output = [6, 17, 15, 12, 1, 24];

짝수 12, 24, 6은 원래 차지하던 인덱스 0, 3, 5의 자리를 그대로 유지한 채 오름차순으로 배치되어 6, 12, 24가 되고, 홀수 17, 15, 1은 인덱스 1, 2, 4에 위치한 상태로 내림차순으로 배치됩니다.

접근 방법

이 문제는 다음 세 단계로 해결할 수 있습니다.

배열을 한 번 순회하면서 홀수가 위치한 인덱스와 짝수가 위치한 인덱스를 각각 별도의 배열에 기록합니다.
원본 배열을 오름차순으로 정렬합니다.
정렬된 배열을 다시 순회하면서 짝수는 기록해 둔 짝수 인덱스에 앞쪽부터 채우고, 홀수는 홀수 인덱스에 뒤쪽부터 채웁니다.

홀수를 뒤쪽 인덱스부터 채우는 이유는 간단합니다. 오름차순으로 정렬된 배열의 홀수들을 역방향으로 배치하면, 왼쪽에서 오른쪽으로 읽었을 때 자연스럽게 내림차순이 되기 때문입니다.

구현 코드

const arr = [12, 17, 15, 24, 1, 6];

const specialSort = (nums = []) => {
  const oddArr = [], evenArr = [];

  // 홀수/짝수가 위치한 인덱스를 각각 기록
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] & 1) {
      oddArr.push(i);
    } else {
      evenArr.push(i);
    }
  }

  // 배열을 오름차순으로 정렬
  nums.sort((a, b) => a - b);

  let odd = oddArr.length - 1, even = 0;
  const res = [];

  // 정렬된 값을 원래 위치에 재배치
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] & 1) {
      res[oddArr[odd--]] = nums[i]; // 홀수는 뒤에서부터
    } else {
      res[evenArr[even++]] = nums[i]; // 짝수는 앞에서부터
    }
  }

  return res;
};

실행 결과

[ 6, 17, 15, 12, 1, 24 ]

복잡도 및 참고 사항

시간 복잡도는 정렬 단계가 지배하므로 O(n log n)이며, 공간 복잡도는 결과 배열과 인덱스 배열로 인해 O(n)입니다. 한 가지 주의할 점은 Array.prototype.sort()가 원본 배열을 직접 변경한다는 것입니다. 원본 배열을 보존해야 하는 경우에는 [...nums]처럼 복사본을 만들어 정렬하는 것이 안전합니다.