JavaScript로 배열을 웨이브 패턴으로 정렬하는 방법

문제 이해하기

숫자 배열 arr를 유일한 인수로 받아, 정렬 후 요소들이 다음과 같은 패턴을 따르도록 만드는 JavaScript 함수를 작성해야 합니다.

arr[0] < arr[1] > arr[2] < arr[3]...

쉽게 말해, 값이 오르락내리락하는 '웨이브(wave)' 모양으로 배열을 재배치하는 것입니다. 예를 들어 다음과 같은 입력이 주어지면,

const arr = [1, 5, 1, 1, 6, 4];

가능한 출력 중 하나는 다음과 같습니다. 조건만 만족하면 여러 가지 정답이 존재할 수 있습니다.

const output = [1, 6, 1, 5, 1, 4];

해결 아이디어

가장 직관적인 접근 방법은 배열을 먼저 오름차순으로 정렬한 뒤, 두 그룹으로 나누어 번갈아 배치하는 것입니다.

1. 오름차순 정렬: 배열 전체를 작은 값부터 큰 값 순서로 정렬합니다.
2. 절반 분할: 앞쪽 절반(작은 값 그룹)과 뒤쪽 절반(큰 값 그룹)으로 나눕니다. 배열 길이가 홀수라면 중앙값을 작은 값 그룹에 포함시켜, 작은 값 그룹이 하나 더 많은 요소를 갖도록 합니다. 이렇게 하면 중복된 값이 많은 배열에서도 패턴이 깨질 가능성을 줄일 수 있습니다.
3. 번갈아 배치: 짝수 인덱스(0, 2, 4...)에는 작은 값 그룹에서 큰 값부터 꺼내 채우고, 홀수 인덱스(1, 3, 5...)에는 큰 값 그룹에서 큰 값부터 꺼내 채웁니다.

그 결과 짝수 인덱스에는 '골짜기'가, 홀수 인덱스에는 '봉우리'가 자연스럽게 형성됩니다.

구현 코드

const arr = [1, 5, 1, 1, 6, 4];

const unevenSort = (arr = []) => {
    // 1. 오름차순 정렬
    arr.sort((a, b) => a - b);

    // 2. 분할 기준점 계산 (길이가 홀수면 중앙값을 작은 그룹에 포함)
    let mid = Math.floor(arr.length / 2);
    if (arr.length % 2 === 1) {
        mid += 1;
    }

    // 3. 두 그룹으로 분할
    const even = arr.slice(0, mid); // 작은 값 그룹
    const odd = arr.slice(mid);     // 큰 값 그룹

    // 4. 인덱스에 맞춰 뒤에서부터 번갈아 배치
    for (let i = 0; i < arr.length; i++) {
        if (i % 2 === 0) {
            arr[i] = even.pop();
        } else {
            arr[i] = odd.pop();
        }
   }
};

unevenSort(arr);
console.log(arr);

실행 결과

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

[ 1, 6, 1, 5, 1, 4 ]

결과를 살펴보면 1 < 6 > 1 < 5 > 1 < 4 순서로, 요구한 웨이브 패턴을 정확히 따르는 것을 확인할 수 있습니다.

복잡도 및 정리

이 알고리즘의 시간 복잡도는 정렬 단계가 지배적이므로 O(n log n)이며, 두 개의 임시 배열을 사용하므로 공간 복잡도는 O(n)입니다. 정렬 후 한 번의 순회만으로 결과를 만들기 때문에 구현이 단순하고, 중복 값이 많은 배열에서도 안정적으로 동작한다는 장점이 있습니다.