JavaScript로 배열을 최대·최소 교차 형태로 재정렬하는 방법

숫자 배열을 입력받아 요소들을 가장 큰 값 → 가장 작은 값 → 두 번째로 큰 값 → 두 번째로 작은 값 순서로 재배치하는 함수 minMax()를 작성해 보겠습니다.

문제 이해하기

예를 들어 다음과 같은 입력 배열이 있다고 가정해 봅시다.

// 입력 배열:
const input = [1, 2, 3, 4, 5, 6, 7]
// 기대되는 출력 결과:
const output = [7, 1, 6, 2, 5, 3, 4]

즉, 정렬된 배열에서 가장 큰 값과 가장 작은 값을 번갈아 배치하다 보면, 마지막에 남은 중간값이 자연스럽게 배열의 끝에 위치하게 됩니다.

구현 코드

const input = [1, 2, 3, 4, 5, 6, 7];
const minMax = arr => {
    const array = arr.slice();
    array.sort((a, b) => a - b);
    for(let start = 0; start < array.length; start += 2){
        array.splice(start, 0, array.pop());
    }
    return array;
};
console.log(minMax(input));

실행 결과

콘솔에 출력되는 결과는 다음과 같습니다.

[
    7, 1, 6, 2,
    5, 3, 4
]

코드 동작 원리

이 알고리즘은 세 단계로 나누어 이해할 수 있습니다.

1. 원본 배열 복사: arr.slice()를 사용해 원본 배열을 변경하지 않고 복사본을 만듭니다. 이렇게 하면 원래 데이터가 손상되지 않습니다.

2. 오름차순 정렬: array.sort((a, b) => a - b)로 배열을 오름차순으로 정렬합니다. 비교 함수를 반드시 전달해야 숫자가 문자열처럼 취급되는 기본 정렬 동작을 피할 수 있습니다.

3. 최대값 삽입 반복: 인덱스 0부터 2칸씩 건너뛰며(start += 2) 반복문을 돌립니다. 각 반복마다 array.pop()으로 배열의 끝(현재 최대값)을 꺼낸 뒤, splice(start, 0, ...)로 짝수 번째 위치에 삽입합니다. 그 결과 가장 큰 값, 가장 작은 값, 두 번째로 큰 값, 두 번째로 작은 값이 차례로 교차 배치됩니다.

시간 복잡도

정렬 단계가 지배적이므로 시간 복잡도는 O(n log n)입니다. 배열의 길이가 n일 때 실용적인 수준의 성능을 보여주며, 대부분의 일반적인 사용 사례에 적합한 방식입니다.