49. Group Anagram

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

Group Anagrams - LeetCode

난이도 : medium

문제

문자열을 배열을 받아 애너그램 단위로 그룹핑 하라.

'애너그램'이란

일종의 언어유희로 문자를 재배열하여 다른 뜻을 가진 단어로 바꾸는 것을 말한다. 우리말을 예를 들면 '문전박대'를 '대박전문'으로 바꿔 부르는 단어 등을 들 수 있다.

 

문제에서 주어진 사항중 문자열 배열의 최대 크기는 10^4 이다. 이는 이중 반복문으로 풀면 time limited 가 날 여지가 있다. 또한 반환되는 문자열 배열은 순서가 상관없다 하였으니 같은 따로 정렬을 할 필요는 없다.

 

1. 문자열을 순회하며 원본 문자는 정렬을 한다. 정렬된 문자는 map 에 key 로 삽입하고 원본문자는 value 로 삽입한다.

예를 들면 eat, tea, ate 의 경우 정렬을 하면 aet 로 모두 같다.

2. 이중 string vector 를 선언하여 map 에 있는 value 를 모두 삽입하여 반환한다.

같은 키를 갖고 있음으로

 

코드

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

        unordered_map<string, vector<string>> m;
        for (string s : strs) {
            string s1 = s;
            sort(s1.begin(), s1.end());
            m[s1].push_back(s);
            // map["ate"] 는 의 값은 vector<string> 으로 "eat", "tea", "ate" 를 갖게 된다.
        }

        vector<vector<string>> sol;
        for (auto it = m.begin(); it != m.end(); it++) {
            vector<string> cur;
            for (string s : it->second) {
                cur.push_back(s);
            }
            sol.push_back(cur);
        }
        return sol;
    }
};