[LeetCode 49] Group Anagrams (Java)

---

풀이

이 문제는 문자열 배열 strs가 주어졌을 때, 애너그램들끼리 그룹으로 묶어 리턴하는 문제이다.

애너그램이란, 단어(word)나 구(phrase)가 주어져있을 때, 문자를 재배열해서 만들어지는 새로운 단어나 구를 말한다.

따라서, 애너그램들은 각 문자들의 개수가 동일하다는 특성을 가지고 있고, 사전순으로 문자들을 정렬했을 때 항상 같은 값을 가지게 된다는 특성을 가지고 있다.

이번 풀이에서는 문자를 정렬했을 때, 애너그램들 끼리는 동일하다는 성질을 이용해 문제를 해결해 보자.

먼저, 애너그램이 같은 문자열들을 그룹화해야하므로, Map<String, List<String>>타입의 맵에 문자열들을 저장해야할 것이다.

다음으로, strs의 원소인 문자열 str에 대해 어떤 처리를 해야하는 지 살펴보자.
1. 문자 배열을 가져온다.
2. 문자 배열을 정렬한다.
3. 정렬된 문자 배열로 문자열을 만든다. (애너그램이라면 모두 동일한 문자열이 만들어 질 것이다.)
4. 해당 문자열을 key로 갖는 리스트에 str을 추가한다.

리턴값이 List<List<String>>타입이므로 Collection를 바탕으로 새로운 ArrayList를 생성하여 리턴하면 될 것이다.

이를 코드로 옮기면 다음과 같다.

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String key = String.valueOf(chars);
            groups.putIfAbsent(key, new ArrayList<>());
            groups.get(key).add(str);
        }

        return new ArrayList<>(groups.values());
    }
}