문제 이해하기
이번 문제에서는 문자열을 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다.
함수는 문자열에 포함된 문자들을 재배치하여 동일한 두 문자가 서로 인접하지 않도록 만들어야 합니다.
만약 그러한 배치가 하나라도 존재한다면 함수는 재배치된 문자열을 반환하고, 불가능하다면 빈 문자열을 반환해야 합니다.
예시
입력 문자열이 다음과 같다고 가정해 보겠습니다.
const str = 'add';
이 경우 함수의 출력은 다음과 같을 수 있습니다.
const output = 'dad';
'add'에서 같은 문자 'd'가 연속으로 붙어 있지만, 재배치한 'dad'에서는 모든 동일한 문자가 서로 떨어져 있는 것을 확인할 수 있습니다.
접근 방법
이 문제를 해결하는 핵심 아이디어는 다음과 같습니다.
1. 각 문자의 등장 횟수를 해시 맵(객체)으로 계산합니다.
2. 가장 많이 등장한 문자부터 내림차순으로 정렬합니다.
3. 가장 빈도가 높은 문자가 전체 길이의 절반(홀수 길이인 경우 절반 올림)보다 많다면, 어떻게 배치해도 인접하게 되므로 즉시 빈 문자열을 반환합니다.
4. 결과 배열의 짝수 인덱스(0, 2, 4...)부터 차례대로 문자를 채우고, 끝에 도달하면 홀수 인덱스(1, 3, 5...)로 돌아가며 채웁니다. 이렇게 하면 같은 문자가 항상 한 칸 이상 떨어지게 됩니다.
구현 코드
위 접근 방식을 구현한 코드는 다음과 같습니다.
const str = 'add';
const formatString = (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 flag = str.length % 2 ? (Math.floor(str.length / 2) + 1) : str.length / 2;
if(map[keys[0]] > flag){
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(formatString(str));실행 결과
콘솔 출력은 다음과 같습니다.
dad
코드 설명
이 알고리즘의 시간 복잡도는 문자 개수 정렬에 O(n log k)(k는 고유 문자 수), 전체적으로 O(n) 수준으로 효율적입니다.
핵심은 짝수 인덱스를 먼저 모두 채운 뒤 홀수 인덱스를 채우는 방식입니다. 예를 들어 'aabb'의 경우, 'a'가 인덱스 0과 2에, 'b'가 인덱스 1과 3에 배치되어 'abab'라는 유효한 결과가 만들어집니다.
만약 'aaa'처럼 한 문자가 전체 길이의 절반을 초과하는 경우에는 어떤 순서로 배치하더라도 인접이 피할 수 없으므로, 사전에 검사하여 빈 문자열을 반환함으로써 불필요한 연산을 줄일 수 있습니다.