LeetCode - 49. Group Anagrams

애너그램 찾기.

처음에는 strs 안에 있는 값들을 정렬할까 했는데, 기존 값을 유지해야돼서 패스.

다음에 생각한 풀이로는 set을 만들어서 set이 동일한지 비교하기.

구현해봤으나 중복 문자가 있는 경우도 있어서 이 경우 실패했다.

그래서 생각한 방법은 map을 사용해서 각 str이 저장하고 있는 알파벳 개수를 저장하고 map끼리 비교!

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<map<char, int>> maps;
        vector<vector<string>> answer;
        for (auto i: strs) {
            map<char, int> tmp;
            for (auto j: i) {
                if (tmp.find(j) == tmp.end())
                    tmp[j] = 0;
                else
                    tmp[j]++;
            }
            maps.push_back(tmp);
        }
        int index = 0;
        vector<int> visited(strs.size(), 0);
        for (int i = 0; i < strs.size(); i++) {
            if (visited[i]) continue;
            vector<string> tmp2;
            tmp2.push_back(strs[i]);
            visited[i] = 1;
            for (int j = i + 1; j < strs.size(); j++) {
                if (visited[j]) continue;
                if (maps[i] == maps[j]) {
                    tmp2.push_back(strs[j]);
                    visited[j] = 1;
                }
            }
            answer.push_back(tmp2);
        }
        return answer;
    }
};

통과는 됐지만 엄청나게 느리게 나왔다.

 

그래서 풀이를 보니.. map을 사용하는데 key를 정렬된 string, value를 key와 애너그램인 원본 string의 배열이었다!

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> s_map;
        vector<vector<string>> answer;
        for (auto i: strs) {
            string tmp = i;
            sort(tmp.begin(), tmp.end());
            s_map[tmp].push_back(i);
        }
        for (auto &i: s_map) {
            answer.push_back(i.second);
        }

        return answer;
    }
};

엄청나게 빨라졌다.

Key Idea

해시맵 사용. 해시맵의 key와 value로 어떤 걸 할지 생각.