[algo/NeetCode] group anagrams

아주 오랜만에 알고리즘 풀었는데 옛날엔 할 게 많아 하기 싫었는데 그래도 다시 하니 재밌긴 합니다.

문제 링크

cpp 정리

• unordered_map<int, vector<string>> um; 에서 원소 삽입할 때 키가 없으면
  - 키가 없으면 빈 std::vector<std::string>을 자동으로 생성한 뒤 참조를 반환함
  - 그래서 바로 push_back이나 emplace_back 사용 가능
• for (auto& [key, vec] : um) 으로 하면 key와 value 탐색 가능
• std::sort는 반환값이 없는 void 함수 → 원본 데이터를 in-place로 수정함

처음 시도

class Solution {
public:

    static constexpr int M = 20000;
    int hash_func(string& str) {
        const int a = 1000;
        int h = 0;
        for (auto& s: str) {
            h = (h*a + s) % M;
        }
        return h % M;
    }

    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> result;
        unordered_map<int, vector<string>> um;

        for (auto& str : strs) {
            int h = hash_func(str);
            um[h].push_back(str);
        }

        for(auto& [key, vec]: um) {
            result.push_back(vec);
        }

        return result;

    }
};

• compilation error 이유
  - 클래스 멤버 함수 내부에 함수 선언 → 컴파일 에러
  - 해결1 :람다 함수 사용하기

		auto hash_func = [M](const string& str) {
            const int a = 1000;
            int h = 0;
            for (auto& s: str) {
                h = (h * a + s) % M;
            }
            return h % M;
        };

    - 해결2 : 클래스 멤버 함수를 분리

• 알고리즘 로직도 문제 있음
  - 위 해시 함수는 문자 순서에 따라 값이 달라짐 → "eat"와 "tea"는 서로 다른 해시값 나옴
  - 해시값이 우연히 겹치면 같은 그룹으로 되어서 오답
  - 해결 : 문자열 정렬 → 정렬된 문자를 key로 하여 문자 빈도 카운팅하기

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> um;
        const int M = 20000;
        vector<vector<string>> result;
        result.resize(20003);

        for (auto& str: strs) {
            string s = sort(str.begin(), str.end());
            um[s].push_back(str);
        }

        for (auto& [key, vec] : um) {
            result.push_back(vec);
        }

        return result;
    }
};

• std::sort는 반환값이 없는 void 함수 → 원본 데이터를 in-place로 수정함
• 문자열 복사 필요 → 복사본을 sort 하기

정답

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> um;
        const int M = 20000;
        vector<vector<string>> result;

        for (auto& str: strs) {
            string s = str;
            sort(s.begin(), s.end());
            um[s].push_back(str);
        }

        for (auto& [key, vec] : um) {
            result.push_back(vec);
        }

        return result;
    }
};