아나그램이란?
아나그램(Anagram)은 같은 문자들을 서로 다른 순서로 재배열하여 만들 수 있는 두 단어 또는 문구를 의미합니다. 예를 들어 'rat'과 'tar'는 동일한 알파벳 r, a, t로 구성되어 있으므로 서로의 아나그램이라고 할 수 있습니다.
문제 상황
아나그램 관계에 있는 문자열들이 포함될 수 있는 문자열 배열을 입력받는 JavaScript 함수를 작성해야 합니다. 이 함수는 모든 아나그램들을 별도의 하위 배열로 묶어 새로운 배열 형태로 반환해야 합니다.
예를 들어, 다음과 같은 입력 배열이 주어졌다고 가정해 보겠습니다.
const arr = ['rat', 'jar', 'tar', 'raj', 'ram', 'arm', 'mar', 'art'];
그렇다면 출력 배열은 다음과 같은 형태가 되어야 합니다.
const output = [ ['rat', 'tar', 'art'], ['jar', 'raj'], ['ram', 'arm', 'mar'] ];
해결 접근 방식
이 문제의 핵심 아이디어는 간단합니다. 아나그램끼리는 문자를 정렬하면 반드시 동일한 문자열이 된다는 점을 활용하는 것입니다.
예를 들어 'rat', 'tar', 'art'를 각각 알파벳 순으로 정렬하면 모두 'art'가 됩니다. 따라서 각 문자열을 정렬한 결과를 키(key)로 사용하고, 원본 문자열들을 값(value)으로 저장하는 Map 자료구조를 사용하면 효율적으로 그룹화할 수 있습니다.
코드 구현
다음은 위 접근 방식을 구현한 전체 코드입니다.
const arr = ['rat', 'jar', 'tar', 'raj', 'ram', 'arm', 'mar', 'art'];
const groupSimilarWords = (arr = []) => {
if (arr.length === 0){
return arr;
};
const map = new Map();
for(let str of arr){
let sorted = [...str];
sorted.sort();
sorted = sorted.join('');
if(map.has(sorted)){
map.get(sorted).push(str);
}else{
map.set(sorted, [str])
};
};
return [...map.values()];
};
console.log(groupSimilarWords(arr));코드 동작 원리
코드의 실행 흐름을 단계별로 살펴보겠습니다.
1단계: 빈 배열 처리
입력 배열이 비어 있는 경우에는 그대로 빈 배열을 반환하여 불필요한 연산을 방지합니다.
2단계: 문자열 정렬
스프레드 연산자([...str])를 사용해 문자열을 개별 문자 배열로 분리한 뒤, sort() 메서드로 알파벳순 정렬하고 join('')으로 다시 하나의 문자열로 합칩니다. 이 정렬된 문자열이 해당 아나그램 그룹의 고유한 키가 됩니다.
3단계: Map에 그룹화
정렬된 키가 Map에 이미 존재하면 기존 배열에 현재 문자열을 추가하고, 존재하지 않으면 새로운 키와 함께 새 배열을 생성합니다.
4단계: 결과 반환
마지막으로 map.values()를 스프레드 연산자로 펼쳐 그룹화된 2차원 배열을 반환합니다.
실행 결과
위 코드를 실행하면 콘솔에 다음과 같은 출력이 나타납니다.
[ [ 'rat', 'tar', 'art' ], [ 'jar', 'raj' ], [ 'ram', 'arm', 'mar' ] ]
'rat', 'tar', 'art'가 한 그룹으로, 'jar'와 'raj'가 한 그룹으로, 'ram', 'arm', 'mar'가 한 그룹으로 올바르게 묶인 것을 확인할 수 있습니다.
시간 복잡도
n개의 문자열이 있고 각 문자열의 최대 길이가 k라고 할 때, 각 문자열을 정렬하는 데 O(k log k)의 시간이 소요되므로 전체 시간 복잡도는 O(n · k log k)입니다. 공간 복잡도는 Map에 저장되는 데이터 크기에 비례하여 O(n · k)입니다. 이는 아나그램 그룹화 문제에서 가장 널리 사용되는 효율적인 해결 방식입니다.