[LeetCode]그룹 애너그램

문제

1. 문자열을 뒤집는 함수를 작성하라. 입력값은 문자 배열이며, 리턴 없이 리스트 내부를 직접 조작하라

• Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

• Example 2:

Input: strs = [""]
Output: [[""]]

• Example 3:

Input: strs = ["a"]
Output: [["a"]]

코드

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs)
    {
    vector<string> temp = strs;
	vector<vector<string>> ans;
	multimap<string, string> mstr;
	for (int i = 0; i < temp.size(); i++)
	{
		sort(temp[i].begin(), temp[i].end());
		mstr.insert({ temp[i] , strs[i]});
	}

	vector<string> a;
	auto iter = mstr.begin();
	while (iter != mstr.end())
	{
		for (auto miter = mstr.lower_bound(iter->first); miter != mstr.upper_bound(iter->first); miter++)
		{
			a.push_back(miter->second);
		}
		ans.push_back(a);
        a.clear();
		iter =  mstr.upper_bound(iter->first);
	}
    return ans;
    }
};

풀이

1.

multimap<string, string> mstr;

• key값으로는 정렬된 문자, value 값으로는 정렬되기전 원래의 문자를 넣는다.

2.

for (int i = 0; i < temp.size(); i++)
	{
		sort(temp[i].begin(), temp[i].end());
		mstr.insert({ temp[i] , strs[i]});
	}

• 예제가 할당된 temp vector의 각 단어들을 정렬한 후 똑같은 단어로 만들어 준다.
• mstr에 key값으로 정렬된 문자, value값으로는 바뀌기전 원래의 문자를 넣어 준다.

3.

vector<string> a;
//1. iter
while (iter != mstr.end())
	{	
    	//2.
		for (auto miter = mstr.lower_bound(iter->first); miter != mstr.upper_bound(iter->first); miter++)
		{
			a.push_back(miter->second);
		}
        //3.
		ans.push_back(a);
        a.clear();
        //4.
		iter =  mstr.upper_bound(iter->first);
	}

1. mstr에는 동일한 key값이 오름차순로 차례대로 정렬되어 있는데, key값을 기준으로 시작부분과 끝나는 부분을 bound 기능으로 알 수 있다. 이렇게 value값들을 a vector에 push_back해서 모아준다.

2. 한 그룹이 a에 모인다면 이차원벡터 ans에 push_back 해준다. 그리고 a를 비워준다.

3. upper_bound는 한 key가 끝나고 다음 부분을 가리킨다. 따라서 다음 key의 반복자 부터 시작하기 위해 현재 반복자의 key의 upper_bound를 iter에 다시 할당한다.

결과

Runtime 50 ms / Memory 19.5 MB
https://leetcode.com/problems/group-anagrams/submissions/879979434/

---

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