[LeetCode] 49. Group Anagrams

문제 출처: https://leetcode.com/problems/group-anagrams/

Group Anagrams - LeetCode

---

문제

문자열 배열 strs 가 주어지면, 애너그램(anagram, 어구전철)을 함께 묶어라. 배열 내의 순서와 상관없이 반환해도 된다.

 

애너그램이란, 단어 혹은 어구의 문자 순서를 재배치하여 원래의 단어 혹은 어구와 정확히 일치하는 단어 혹은 어구를 말한다.

예제

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Input: strs = [""]
Output: [[""]]

Input: strs = ["a"]
Output: [["a"]]

---

풀이

애너그램이 동일한 문자로 구성된 단어라는 점에서 착안하여 단어를 구성하는 문자를 알파벳 순으로 정렬하여 애너그램 여부를 파악할 수 있다. 만약 어떤 두 단어가 애너그램이라면 이 두 단어는 알파벳 순으로 정렬한 뒤에는 동일한 단어가 되어 있을 것이다.

애너그램 예시1 _ word1 = eat, word2 = ate

  각 단어 안의 문자를 알파벳 순서로 정렬 
  => word1 = aet, word2 = aet
  => word1 == word2

애너그램 예시2 _ word1 = eat, word2 = cat

  각 단어 안의 문자를 알파벳 순서로 정렬 
  => word1 = aet, word2 = act
  => word1 != word2
  => word1과 word2는 애너그램이 아님!!

이러한 애너그램 단어들을 효율적으로 관리하기 위해서 맵 자료구조를 사용할 수 있다. 알파벳 순서로 정렬된 형태를 키로 하여 값을 추가하는 것이다. 

var groupAnagrams = function(strs) {
    const group = new Map();
    strs.forEach(str => {
        const sortedStr = str.split('').sort((a, b) => a.charCodeAt(0) - b.charCodeAt(0)).join('');
        if (!group.has(sortedStr)) {
            group.set(sortedStr, []);
        }
        group.get(sortedStr).push(str);
    });
    
    const answer = [];
    for (let [ _, g ] of group) {
        answer.push(g);
    }
    return answer;
};

정렬과 맵을 이용한 이 방식의 시간 복잡도를 생각해보자. 배열의 길이가 N이고 배열 내 가장 긴 문자열의 길이가 M이라 할 때, O(N * M * logM)의 시간 복잡도를 갖는 것으로 생각할 수 있다. 이러한 시간 복잡도를 갖는 이유는 최악의 경우 배열 내의 모든 단어의 길이가 M일 수 있기 때문이다.

 

애너그램을 판단하는 방법에는 정렬 대신에 다른 선택지가 있는데, 단어를 구성하는 알파벳을 카운트하는 것이다. 애너그램 관계인 단어는 이 구성이 동일할 것임이 명백하다. 여러 단어에 대해서 애너그램을 판단하고 저장하기 위해서 마찬가지로 맵을 이용할 수 있고 키(key)를 다음과 같이 만들어 사용할 수 있다.

예시 단어: eat

알파벳 카운트: a: 1, e: 1, t: 1
키: 1a1e1t

단순하게 카운트 값과 해당 문자를 엮어서 하나의 문자열로 만드는 것이다.

var groupAnagrams = function(strs) {
    const group = new Map();
    strs.forEach(str => {
        const key = countChar(str);
        if (!group.has(key)) {
            group.set(key, []);
        }
        group.get(key).push(str);
    });
    
    const answer = [];
    for (let [ _, g ] of group) {
        answer.push(g);
    }
    return answer;
};

var countChar = function (str) {
    const charArr = new Array(26).fill(0);
    for (const ch of str.split('')) {
        charArr[ch.charCodeAt(0) - 'a'.charCodeAt(0)] += 1;
    }
    
    let ans = '';
    for (let i = 0; i < 26; i++) {
        if (charArr[i] !== 0) {
            ans += String.fromCharCode(i + 'a'.charCodeAt(0)) + charArr[i].toString();
        }
    }
    
    return ans;
}

이 방식의 시간 복잡도를 생각해보면, 배열의 길이가 N, 배열 내 가장 긴 문자열이 M이라 할때 O(N * M)이 된다.

 

Github: 49.js

GitHub - opwe37/Algorithm-Study