[LeetCode] 49 - Group Anagrams

문제

• 링크: https://leetcode.com/problems/group-anagrams
• 난이도: Medium
• 태그: 배열, 해시 테이블, 문자열, 정렬
• 결과: Time: 3 ms (99.98%), Space: 24.88 MB (86.71%)

풀이

map 사용

class Solution {
private:
struct chnum
{
    int cnt[26];

    chnum()
    {
        memset(cnt, 0, sizeof(int) * 26);
    }

    bool operator<(const chnum& other) const
    {
        for (int i = 0; i < 26; ++i)
        {
            if (this->cnt[i] != other.cnt[i])
            {
                return this->cnt[i] < other.cnt[i];
            }
        }

        return false;
    }
};

public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {

        map<chnum, vector<string>> ns;
        for (auto& str : strs)
        {
            chnum n;
            for (auto ch : str)
            {
                n.cnt[ch - 'a']++;
            }

            ns[n].push_back(str);
        }

        vector<vector<string>> v;

        for (auto p : ns)
        {
            v.push_back(p.second);
        }

        return v;
    }
};

단어의 알파벳 구성을 확인하여 맵의 Key로 사용하고, 동일한 알파벳 구성을 갖는 단어의 배열을 Value로 두면 된다. map을 사용하기 위해 operator<을 오버로딩 했다.

unordered_map 사용

class Solution {
private:
    struct chnum
    {
        int cnt[26];

        chnum()
        {
            memset(cnt, 0, sizeof(int) * 26);
        }

        bool operator==(const chnum& other) const
        {
            for (int i = 0; i < 26; ++i)
            {
                if (this->cnt[i] != other.cnt[i]) return false;
            }
            return true;
        }
    };

struct chnumHash
    {
        size_t operator()(const chnum& key) const
        {
            size_t seed = 0; 
            for (int i = 0; i < 26; ++i)
            {
                seed = ((seed << 5) - seed) + key.cnt[i];
            }
            return seed;
        }
    };

public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<chnum, vector<string>, chnumHash> ns;
        for (auto& str : strs)
        {
            chnum n;
            for (auto ch : str)
            {
                n.cnt[ch - 'a']++;
            }

            ns[n].push_back(str);
        }

        vector<vector<string>> v;
        v.reserve(ns.size());

        for (auto& p : ns)
        {
            v.push_back(move(p.second));
        }

        return v;
    }
};

원리는 같은데, 일반적인 구현상 내부적으로 레드블랙 트리가 아니라 해시맵을 사용하는 unordered_map을 채택한 코드이다. 이를 위해 operator==을 오버로딩하고 chnumHash클래스를 추가해 operator()을 오버로딩했다.

해싱 방식은 Java에서 hashCode 메소드를 사용할 때 처럼 31을 곱해서 값을 더하는 식으로 구현했다.

속도는 역시나 이 쪽이 더 빨랐다.

정렬 사용

나의 풀이는 아닌데, 스터디원의 풀이를 보니 문자열을 배열로서 정렬하여 맵의 키로 사용하는 풀이가 있었다. JS를 사용하셨는데, 문법이 아주 신기했다.

배운 점과 후기

map과 unordered_map을 사용하기 위해 오버로딩 해야하는 연산자가 무엇인지 외워두는 것이 좋겠다. 후자의 경우 operator==를 오버로딩 해야한다는 사실을 알지 못했다.

이 포스트는 달레 스터디(5주차)에서 진행한 Blind 75 문제집 풀이의 일부입니다.