JavaScript로 같은 문자가 일정 거리 이상 떨어지도록 문자열 재배치하기

문제 상황

첫 번째 인수로 문자열 str을, 두 번째 인수로 숫자 num(문자열 길이보다 작은 값)을 받는 JavaScript 함수를 작성해야 합니다.

이 함수는 문자열 str의 문자들을 재배치하여 새로운 문자열을 만들어야 하며, 이때 같은 문자끼리는 최소 num칸 이상 떨어져 있어야 합니다. 즉, 동일한 문자가 서로 너무 가까운 위치에 배치되지 않도록 순서를 조정하는 것이 핵심입니다.

함수는 최종적으로 새로 구성된 문자열을 반환하며, 만약 그러한 배치가 불가능한 경우에는 빈 문자열("")을 반환해야 합니다.

예를 들어 함수의 입력이 다음과 같다면 −

const str = 'kkllmm';

출력 결과는 다음과 같아야 합니다 −

const output = 'mlmklk';

구현 예시

이 문제를 해결하는 코드는 다음과 같습니다 −

const str = 'kkllmm';
const placeApart = (str = '') => {
    // 각 문자의 등장 횟수를 카운트
    const map = {};
    for(let i = 0; i < str.length; i++){
        map[str[i]] = map[str[i]] || 0;
        map[str[i]]++;
    }
    // 빈도수를 기준으로 내림차순 정렬
    let keys = Object.keys(map).sort((a, b) => {
        if(map[a] < map[b])
            return 1;
        return -1;
    });
    // 가장 많은 문자가 절반을 초과하면 배치 불가
    let len = str.length % 2 ? (Math.floor(str.length / 2) + 1) : str.length / 2;
    if(map[keys[0]] > len){
        return "";
    }
    // 짝수 인덱스부터 채우고, 부족하면 홀수 인덱스로 이동
    const res = [];
    let index = 0, max = str.length - 1;
    while(keys.length){
        let currKey = keys.shift();
        let count = map[currKey];
        while(count){
            res[index] = currKey;
            index = index + 2;
            if(index > max)
                index = 1;
            count--;
        }
    }
    return res.join("");
};
console.log(placeApart(str));

코드 동작 원리

위 코드의 핵심 로직을 단계별로 살펴보면 다음과 같습니다.

1단계 — 빈도수 계산: 객체(map)를 활용해 각 문자가 몇 번 등장하는지 집계합니다.

2단계 — 배치 가능 여부 판단: 특정 문자의 개수가 전체 길이의 절반(홀수 길이인 경우 절반 + 1)을 초과하면, 아무리 배치해도 해당 문자들이 인접하게 됩니다. 이 경우 함수는 즉시 빈 문자열을 반환합니다.

3단계 — 교차 배치: 빈도수가 높은 문자부터 차례대로 0, 2, 4…와 같은 짝수 인덱스에 배치합니다. 짝수 인덱스가 모두 소진되면 1, 3, 5…와 같은 홀수 인덱스로 이동하여 이어서 채웁니다. 이렇게 하면 같은 문자 사이에 반드시 다른 문자가 하나 이상 끼어 들게 됩니다.

참고로 위 구현은 같은 문자가 최소 2칸 이상 떨어지도록 배치하는 방식으로, 인접한 위치에 동일 문자가 오는 것을 방지합니다.

출력 결과

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

mlmklk

출력된 문자열 'mlmklk'를 보면 같은 문자들이 서로 붙어 있지 않고 최소 한 칸 이상 떨어져 배치된 것을 확인할 수 있습니다.