[LeetCode] 49. Group Anagrams

LeetCode - 49. Group Anagrams 알고리즘 문제 풀이

분류

문제 링크 : https://leetcode.com/problems/group-anagrams/

풀이

strs에 들어있는 문자열을 아나그램으로 표현했을 때의 결과가 같다면, 그 결과가 같은 문자열끼리 동일한 벡터로 구분지어 반환하는 문제이다.

(eat와 tae는 동일한 알파벳과 동일한 알파벳 개수가 사용되었기 때문에 아나그램이다.)

아나그램을 확인하기 위해 해시를 사용했는데, 그러기 위해서는 사용한 문자열의 순서는 무관하게 사용된 문자열 자체만 판별해야 했으므로 사용된 알파벳 개수를 세는 카운트 배열(cnt)을 통해 문자열의 해시값을 구했다.

카운트 배열은 a부터 z가 사용됐는지 순서대로 확인하기 때문에 eat와 tae처럼 알파벳 순서가 달라도 결국 동일한 해시값을 구하게 된다.

이 해시값은 unordered_map에서 동일한 아나그램을 식별하기 위한 key 역할을 하고 value는 ans벡터 길이를 추가하여 이후에 동일한 아나그램이 들어오면 ans 벡터의 index 위치( ans[index])에 추가하기 위한 인덱스 역할을 한다. (처음 등장한 key값인 경우 ans벡터에 문자열을 추가하고, 현재 key값 위치에 ans의 사이즈를 추가한다.)

소스 코드

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        string shf;
        vector<vector<string>> ans;
        unordered_map<size_t, int> m;
        for (const auto& s : strs) {
            int cnt[26] = { 0 };
            for (int i = 0; s[i] != '\0'; ++i) {
                ++cnt[s[i] - 'a'];
            }
            string hashS;
            for (int i = 0; i < 26; ++i) {
                if (cnt[i] == 0) continue;
                for (int j = 0; j != cnt[i]; ++j) {
                    hashS += ('a' + i);
                }
            }
            hash<string> h;
            size_t key = h(hashS);
            if (m[key] == 0) {
                ans.push_back({ s });
                m[key] = (int)ans.size();
            }
            else {
                ans[m[key] - 1].push_back(s);
            }
        }
        return ans;
    }
};