LeetCode 49. Group Anagrams (ver2)

The link : leetcode.com/problems/group-anagrams/submissions/

Group Anagrams - LeetCode

예전에 이미 풀어본 적이 있었는데, 이때는 해쉬 테이블과 맵의 개념을 몰라서 아는대로 무작정 풀었섰다

다시 도전하게 되었을때는 아래와 같은 방법을 고안했다.

 

1. Unorder_map에 문자열을 저장한다. 이때 Key와 Value는 다음과 같다.

Key : 문자열을 오름차순으로 정렬한 값 

Value : 문자열의 원본 값

2. string 2차원 벡터를 만든다. 여기서 1번에서 구했던 Unordered_map의 Value를 모두 저장시킨다.

 

아이디어까지는 좋았으나, 구현하는데 실수를 많이 겪었다. 아직 Map을 사용하는게 익숙치 못해서 그랬다.

다른이의 해결을 참고하려고 찾아봤는데, 해당 문제의 Discussion에 나와 동일한 아이디어로 구현한 사람이 있어서 그 사람의 코드를 참고해서 구현했다.

 

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>> map;
        vector<vector<string>> ans;
        for(auto s : strs){
            string temp = s;
            sort(temp.begin(),temp.end());
            map[temp].push_back(s);
        }
        for(auto s : map) ans.push_back(s.second); // first = key, second = value
        return ans;
    }
};

 

 

 

위가 Map을 통해 구현한 결과, 아래는 2중 for문을 통해 무작정 구현했던 과거 결과인데, 확실히 Map을 사용하니 효율성이 더 높아졌다.

특히 시간 효율성에서 큰 차이를 보여준다.