[LeetCode] 49. Group Anagrams

https://leetcode.com/problems/group-anagrams/

Group Anagrams - LeetCode

Group Anagrams.

 

 

알파벳 소문자로만 이루어진 string 배열이 주어졌을 때,

각각의 string을 사용된 알파벳을 기준으로 그룹을 만들어 주면 된다.

이 때, 개수도 생각해주어야 한다.

 

예를 들어, eat와 tea 는 a,e,t가 사용되었으므로 같은 그룹이다.

 

이 문제는 번뜩! 떠오른 생각으로 바로 작성하였더니 해결되어 악필 풀이가 없다.

 

그룹을 만들기에 좋은것은 map을 활용하는 것이다.

map을 활용하여 문제를 풀자.

 

map에 저장하는 것은 알겠는데 같은 그룹인지 어떤 그룹에 속할지는 어떻게 알까??

답은 정렬에 있다!

제한조건에서 string이 알파벳 소문자로만 이루어져 있어 간단해진다.

대문자가 섞여도 크게 어렵진 않지만 만약 한글이었다면 매우 복잡해졌을 것.

 

알파벳 소문자는 총 26개다.

소문자로만 된 string이 있을때 어떻게하면 아주 쉽고 빠르게 정렬할 수 있을까?

바로 배열을 사용한 정렬이다.

이는 길이가 n일 때, O(n)의 시간복잡도를 가진다. 

 

방법은 간단하다.

알파벳 소문자를 담을 26길이의 int 배열을 만들어주고, (0으로 세팅)

string의 앞글자부터 차례차례 해당하는 배열을 증가 시킨다.

다 끝났으면 배열의 앞부분부터 배열에 해당하는 알파벳을 배열값만큼 반복해 string에 더해주면 된다.

이 때 이 string을 그룹의 기준으로 삼아주면 된다.

 

string str_sort(string str) {
    string ret;
    int arr[30];
    for (int i=0; i<26; i++) arr[i] = 0;
    for (int i=0; i<str.size(); i++) arr[(int)(str[i]-'a')]++;
    for (int i=0; i<26; i++) for (int j=0; j<arr[i]; j++) ret += (char)(i+'a');
    return ret;
}

 

여기서 char를 ascii 코드값을 이용해 알파벳 순서로 변경하는 방법과 그 반대를 잘 활용하자.

 

 

결과값은 string의 벡터의 벡터로 나타내야 한다.

무슨 말이냐면 string 벡터는 한 그룹을 나타내고,

string 벡터의 벡터는 그룹의 모음이다.

map에 저장을 할때는 key는 위에서 구하게 될 string을, 

value는 string의 벡터의 벡터의 인덱스로 매핑을 해주자.

 

해당 map에 key값으로 위에서 구한 string 값이 있다면, value 번째 인덱스에 해당 문자를 추가해주고,

만약 없다면 map에 key = 정렬된 string, value = vector의 길이를 매핑해주고, vector에는 새로운 vector를 추가하고, 거기에 해당 string을 넣어주자.

 

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    vector<vector<string>> ret;
    map<string, int> m;
    for (auto str:strs) {
        string sorted = str_sort(str);
        if (m.find(sorted)!=m.end()) {
            ret[m[sorted]].push_back(str);
        } else {
            m.insert({sorted, ret.size()});
            ret.push_back(vector<string> {str});
        }
    }
    return ret;
}

 

전체 코드는 아래와 같다.

 

class Solution {
public:
    string str_sort(string str) {
        string ret;
        int arr[30];
        for (int i=0; i<26; i++) arr[i] = 0;
        for (int i=0; i<str.size(); i++) arr[(int)(str[i]-'a')]++;
        for (int i=0; i<26; i++) for (int j=0; j<arr[i]; j++) ret += (char)(i+'a');
        return ret;
    }
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ret;
        map<string, int> m;
        for (auto str:strs) {
            string sorted = str_sort(str);
            if (m.find(sorted)!=m.end()) {
                ret[m[sorted]].push_back(str);
            } else {
                m.insert({sorted, ret.size()});
                ret.push_back(vector<string> {str});
            }
        }
        return ret;
    }
};