[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<vector<string>> result;
		multimap<string, string> mtM_temp;
		stack<string> st;

		for (int i = 0; i < strs.size(); i++)
		{
			string originLetter = strs[i];
			string sortLetter;
			sort(strs[i].begin(), strs[i].end());

			sortLetter = strs[i];

			mtM_temp.insert({ sortLetter, originLetter });
		}

		int resultIndex = 0;
		for (auto a : mtM_temp)
		{
			if (!st.empty())
			{
				if (st.top() != a.first)
				{
					result.push_back(vector<string>());
					resultIndex++;
				}
			}
			else
			{
				result.push_back(vector<string>());
			}
			result[resultIndex].push_back(a.second);
			st.push(a.first);		
		}
		
		return result;
    }
};

풀이

1. Field

		vector<vector<string>> result; //1
		multimap<string, string> mtM_temp; //2
		stack<string> st; //3

1. 결과를 담을 이차원 벡터

2. 과정에서는 문장을 sort한 string이 필요하고, 결과에선 기존의 string이 필요하다.
   그러기 위해서는 2가지의 string을 담을 데이터가 필요하다. unordered를 쓰지 않은 이유는
   sort된 string을 순서대로 담기 위해서다. 그렇게 되면 sort된 string과 비교해서 바뀌는 분기점을 파악할 수 있다.

3. 애너그램을 그룹화 하기 위한 stack 변수이다. 정렬된 이전 string 데이터를 담고 현재 정렬된 string과 비교하여 바뀌는 분기점인지 파악한다.

결과

Runtime 38 ms / Memory 20.18 MB
https://leetcode.com/problems/group-anagrams/submissions/1089100306/

---

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