[leetcode, Medium] Group Anagrams

Given an array of strings, group anagrams together.

Example:

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

All inputs will be in lowercase.
The order of your output does not matter.

풀이방법

우선 anagrams이 뭔지 찾아봤더니 그냥 어떤 문자열내의 문자를 섞었을때 나올 수 있는 다른 문자열들이란 의미였다.

예를들어, eat에서 a를 맨 뒤로 보내면 eta가 된다. 이 둘은 anagram이다.

 

그래서 우선 간단하게 풀 수 있는 방법을 생각해봤다. 각 문자열들을 정렬하면 될것같았다.

하지만 이렇게 할 경우  O(N^2 * logN)의 생각보다 많은 시간이 걸린다. 왜냐면 정렬에 NlogN이 소요되며 인풋 배열을 순회하는데 N이 추가로 소요되기 때문이다.

 

그래서 예전에 잠깐 공부했었던 O(N)짜리 정렬 방법을 찾아보기로 했다. 카운팅 정렬이라는게 존재했다.

이것은 어떤 숫자 배열이 주어졌을때 각 숫자들이 얼마나 많이 등장하는지 배열에 기록해놓고 한번더 순회하면서 각 배열 요소에 기록된 카운팅만큼 인덱스를 출력하여 정렬 하는 방법이다. 

 

이 문제에서는 a부터 z까지 총 26개의 숫자만 존재하기 때문에 카운팅 정렬을 써도 무조건 배열을 26칸밖에 사용하지 않기때문에 메모리를 많이 사용하지도 않는다. 이 방법으로 풀 경우 O(N^2)의 풀이가 가능해진다.

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    const m = new Map();
    const countingSort = (arr) => {
        const temp = Array(26).fill(0);
        for(let i=0; i<arr.length; i++) {
            temp[arr[i]]++;
        }
        const result = [];
        for(let i=0; i<26; i++) {
            for(let j=0; j<temp[i]; j++) {
                result.push(i);
            }
        }
        return result;
    };
    const convertStringToNumbers = str => {
        const result = [];
        for(let i=0; i<str.length; i++) {
            result.push(str[i].charCodeAt() - 97);
        }
        return result;
    }
    for(let i=0; i<strs.length; i++) {
        const numbers = convertStringToNumbers(strs[i]);
        const sortedNumbers = countingSort(numbers);
        const stringNumbers = sortedNumbers.join();
        if(!m.get(stringNumbers)) m.set(stringNumbers, [strs[i]]);
        else m.set(stringNumbers, [...m.get(stringNumbers), strs[i]]);
    }
    const answer = [];
    for(const [key, val] of m) {
        answer.push(val);
    }
    return answer;
};

1. 문자열을 0 ~ 25까지의 숫자 배열로 바꾼다. "cba" -> [2, 1, 0]

2. 숫자 배열을 정렬한다.  [2, 1, 0] -> [0, 1, 2]

3. 정렬된 숫자를 맵의 key로 넣기 위해 join한다. [0, 1, 2] -> "0,1,2"

4. 맵에서 이 string을 key로 사용하여 value에는 원래 문자열을 넣어주면 된다.