LeetCode (C/C++) 49. Group Anagrams

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

---

풀이

1차

문자열을 정렬한 후, 해당 값과 원래 값을 우선순위 큐에 저장.

정렬한 값을 비교하며 같은 값이라면 벡터에 넣어 저장하는 방식으로 구현함

 

2차

1차 풀이가 느려서 다른 풀이를 봤고, 정렬 값 비교를 우선순위 큐가 아닌 unordered_map으로 바꿈

 

3차

2차입력 값의 범위가 소문자 영어로 국한되어 있어 sort 함수 대신 문자의 개수를 세서 정렬하는 방식으로 바꿨으나 2차보다 값이 느리게 나왔다.

---

코드 - 1차 풀이

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> anagrams;
        priority_queue <pair<string, string>> pq;

        // 주어진 문자열을 알파벳 순서로 정렬 후 원본 문자열과 함께 우선순위 큐에 저장
        for (int i = 0; i < strs.size(); i++) {
            string origin = strs[i];
            sort(strs[i].begin(), strs[i].end());
            pq.push({strs[i], origin});
        }

        
        while (pq.size()) {
            string cmp = pq.top().first;
            vector<string> anagram;

            // 정렬된 문자열이 같다 == 같은 anagram이므로 해당 값이 같을 때까지 벡터에 넣음
            while (pq.size() && cmp == pq.top().first) {
                anagram.push_back(pq.top().second);
                pq.pop();
            }

            // anagram끼리 묶은 벡터 삽입
            anagrams.push_back(anagram);
        }
        return anagrams;
    }
};

 

코드 - 2차 풀이

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> anagrams;
        unordered_map <string, vector<string>> um;

        // 주어진 문자열을 알파벳 순서로 정렬 후 원본 문자열과 함께 map에 저장
        for (int i = 0; i < strs.size(); i++) {
            
            string origin = strs[i];
            sort(strs[i].begin(), strs[i].end());

            // 정렬 후 해당 값이 존재하지 않는다면 새로 생성
            if (um.find(strs[i]) == um.end()) {
                vector<string> v;
                
                v.push_back(origin);
                um[strs[i]] = v;
            }
            
            // 존재한다면 value 값 추가
            else
                um[strs[i]].emplace_back(origin);
        }
        
        for (auto iter = um.begin(); iter != um.end(); iter++) {
            anagrams.push_back(iter->second);
        }
        return anagrams;
    }
};

 

코드 - 3차 풀이

class Solution {
public:
    
    string sortStr(string s) {
        int cha[26] = {0, };
        string sortedStr = "";
        
        for(int i = 0; i < s.size(); i++)
            cha[s[i] - 'a']++;
        for(int i = 0; i < 26; i++) {
            for(int j = 0; j < cha[i]; j++)
                sortedStr += i + 'a';
        }
        return sortedStr;
    }

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

        // 주어진 문자열을 알파벳 순서로 정렬 후 원본 문자열과 함께 map에 저장
        for (int i = 0; i < strs.size(); i++) {
            
            string sortedStr = sortStr(strs[i]);

            // 정렬 후 해당 값이 존재하지 않는다면 새로 생성
            if (um.find(sortedStr) == um.end()) {
                vector<string> v;

                v.push_back(strs[i]);
                um[sortedStr] = v;
            }
            
            // 존재한다면 value 값 추가
            else
                um[sortedStr].emplace_back(strs[i]);
        }
        
        for (auto iter = um.begin(); iter != um.end(); iter++) {
            anagrams.push_back(iter->second);
        }
        return anagrams;
    }
};