JavaScript로 인접 중복 없이 배열 요소 재배치하는 방법

문제 상황

리터럴 값들로 이루어진 배열 arr을 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다. 이 배열에는 서로 인접하게 배치된 중복 요소들이 포함되어 있습니다.

우리가 만들 함수는 배열 내에서 같은 값이 두 개 연속으로 나타나지 않도록 요소들을 재배열해야 합니다. 그리고 이러한 배치 방식이 최소 하나 이상 존재한다고 보장되므로, 재배열된 배열을 결과로 반환하면 됩니다.

예를 들어, 함수에 다음과 같은 입력이 주어진다고 가정해 보겠습니다.

const arr = [7, 7, 7, 8, 8, 8];

그렇다면 기대되는 출력은 다음과 같습니다.

const output = [7, 8, 7, 8, 7, 8];

출력 설명

위 출력 외에도 조건을 만족하는 다른 올바른 재배열 결과가 존재할 수 있습니다. 핵심은 동일한 값이 서로 붙어 있지 않기만 하면 된다는 점입니다.

해결 접근 방법

이 문제를 해결하는 전략은 다음과 같습니다.

1. 각 숫자별 등장 횟수를 객체(맵) 형태로 집계합니다.
2. 빈도수를 기준으로 키를 정렬하여, 가장 많이 등장한 숫자부터 우선적으로 사용합니다.
3. 짝수 인덱스 자리와 홀수 인덱스 자리를 나누어 순서대로 값을 채워 넣으면, 같은 값이 인접하지 않게 배치할 수 있습니다.

예제 코드

위 로직을 구현한 코드는 다음과 같습니다.

const arr = [7, 7, 7, 8, 8, 8];
const rearrangeArray = (arr = []) => {
    const map = arr.reduce((acc, val) => {
        acc[val] = (acc[val] || 0) + 1;
        return acc;
    }, {});
    const keys = Object.keys(map).sort((a, b) => map[a] - map[b]);
    const res = [];
    let key = keys.pop();
    for(let i = 0; i < arr.length; i += 2){
        if(map[key] <= 0){
            key = keys.pop();
        };
        map[key] -= 1;
        res[i] = Number(key);
    };
    for(let i = 1; i < arr.length; i += 2){
        if(map[key] <= 0){
            key = keys.pop();
        };
        map[key] -= 1;
        res[i] = Number(key);
    };
    return res;
};
console.log(rearrangeArray(arr));

실행 결과

콘솔에서 실행하면 아래와 같은 결과를 확인할 수 있습니다.

[ 8, 7, 8, 7, 8, 7 ]

코드 설명

먼저 reduce() 메서드를 활용해 각 숫자의 등장 횟수를 계산합니다. 이후 남아 있는 숫자 중 가장 많이 등장한 것부터 꺼내어 짝수 인덱스(0, 2, 4...)에 먼저 배치하고, 이어서 홀수 인덱스(1, 3, 5...)를 채웁니다. 특정 숫자의 잔여 개수가 0 이하가 되면 다음 숫자로 전환하는 방식으로, 결과적으로 모든 인접 요소가 서로 다른 값을 갖게 됩니다.