[Leetcode,c++] Group Anagrams

문제

Group Anagrams - LeetCode

 

코드

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

        map<string,vector<string>>m;
        map<char,int>char_check;

        sort(strs.begin(),strs.end());

        vector<string>temp = strs;

        for(int i=0; i<temp.size(); i++){
            sort(temp[i].begin(),temp[i].end());
            m[temp[i]]={};
        }
        vector<string> origin = strs;

        for(int i=0; i<strs.size(); i++){
            sort(strs[i].begin(),strs[i].end());
            m[strs[i]].push_back(origin[i]);
        }

        vector<vector<string>>ans;

        for(auto i = m.begin(); i!=m.end(); i++){
            ans.push_back(i->second);
        }

      return ans;
    }
};

 

풀이

입력 배열 안의 모든 문자 배열 속의 문자열들을 정렬하여 맵 테이블에 넣습니다. 그 후 strs 배열의 크기만큼 돌면서 정렬 한 문자의 값이 있는 경우 원래 정렬하기 전 문자를 삽입합니다. 그 후 출력합니다.

말재간이 없어서 예를 들어 설명하자면 

["eat","tea","tan","ate","nat","bat"]

위 와 같은 입력이 주어졌을때 먼저 

["ate", "bat", "eat", "nat", "tan", "tea"]

위와 같이 정렬을 시켜줍니다. 그 후  각 문자열들을 정렬 후  맵 테이블에 값들을 삽입하면 

m["aet"]={}, m["abt"] = {}, m= ["ant"] = {}, 

위와 같이 맵 테이블에 값들이 들어갈것입니다. 그 후 

        for(int i=0; i<strs.size(); i++){
            sort(strs[i].begin(),strs[i].end());
            m[strs[i]].push_back(origin[i]);
        }

위 과정을 거치면 m["aet"] ={"ate", "eat", "tea"}, m["abt"] ={"bat"}, m["ant"] = {"nat", "tan"} 의 값이 됩니다.

이제 2차원 벡터에 위 맵테이블의 value 값들을 넣어주고 출력하면 됩니다.