[LeetCode] 49. Group Anagrams (그룹 애너그램)

🔦 문제 링크

🔊 파이썬 알고리즘 인터뷰 책을 참고했습니다.

• 문제

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

애너그램 단어나 구를 하나의 그룹으로 묶어 반환하세요.

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

• 입출력

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

✍️ 풀이

---

• 처음에 하나하나 모든 문자열의 문자에 대해 갯수를 구해 애너그램 그룹을 구했지만 이는 Time out이 발생했다.

• 그 보다는 딕셔너리를 이용해서 각 단어의 구성을 키로 하여 문자를 추가하는 방법이 훨씬 빠르다.

1. collections.defaultdict(list)를 통해 list를 기본 구성으로 지정할 수 있다.
2. sorted()후 에는 리스트로 반환되므로 join()을 통해 다시 문자열로 변환시켜주었다.
3. 변환시킨 문자열을 키로 사용해 애너그램 그룹을 구성할 수 있다.

🛠 코드

• 리스트를 원소를 앞-뒤로 검사하는 가장 기본적인 풀이방법이다.

---

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        sorted_list = []
        anagrams = collections.defaultdict(list)
        for word in strs:
            anagrams[''.join(sorted(word))].append(word)
        return anagrams.values()

📝 정리

---

🎈 참고

---

Book 링크