[LeetCode] 49 Group Anagrams JavaScript

문제 링크

Group Anagrams - LeetCode

 

문제 유형

배열, 문자열

 

문제 풀이

해당 문제는 여러 문자열이 담긴 배열이 입력으로 주어지고, anagram 단어끼리 묶어서 반환하는 문제이다. Anagram은 단어의 순서를 바꿔서 다른 단어를 찾는 놀이를 말한다.

anagram 단어를 묶기 위해 JavaScript의 Map을 사용해 키를 기준으로 anagram 단어를 그룹핑한다. 이때, 기준이 되는 키는 각 문자열을 정렬시킨 문자열이다.
따라서, Map을 생성하고 배열을 순차적으로 접근하면서 해당 문자열을 정렬 시킨다. 정렬된 문자열을 키, 원래의 문자열을 값으로하여 Map에 추가한다. map.values()는 각 요소의 값을 모은 이터러블 객체를 반환한다.
그러므로 각 문자열의 길이를 m, 배열의 길이를 n이라고 하면 O(nmlogm)의 시간복잡도를 갖는다.

 

이외에도 각 문자열의 알파벳 개수를 키(key)로 지정하여 문제를 해결할 수도 있다. 이때는 각 문자열마다 알파벳 테이블을 생성해 알파벳이 나온 횟수를 저장하고, 그것을 이용해 키값을 만들면된다. 이때는 O(nm)의 시간 복잡도를 갖는다.

 

코드

// 키: 정렬된 문자열
var groupAnagrams = function(strs) {
    const map = new Map();
    for (let i = 0; i < strs.length; i++) {
        const key = strs[i].split("").sort().join("");
        if (map.has(key)) {
            map.set(key, [...map.get(key), strs[i]]);
        } else {
            map.set(key, [strs[i]]);
        }
    }

    return [...map.values()];
};

 

참고

https://www.youtube.com/watch?v=5BRmT4VTEpo