[LeetCode] 49. Group Anagrams

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

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

---

• 제일 먼저 접근했던 방식은 strs 를 순회하면서 각각의 단어를 받아온 후, sorted() 를 이용해 소팅한 값을 anagrams리스트에 넣고, 이 리스트의 인덱스를 참조하여 result 리스트에 단어를 추가하는 방식이었다.

  class Solution:
      def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
          anagrams = []
          res = []
          for word in strs:
              word_sorted = sorted(word)
              if word_sorted not in anagrams:
                  anagrams.append(word_sorted)
                  res.append([word])
              else:
                  idx = anagrams.index(word_sorted)
                  res[idx].append(word)
          
          return res

  

• 제출해본 결과 원하는 기능을 수행하긴 하지만, 그 속도가 매우 느린것을 확인할 수 있었다. 해당 단어를 같은 애너그램 그룹으로 묶기 위해선 필수적으로 모든 단어를 소팅해야 하므로, 그 외의 부분에서 해결법을 찾기로 했다.

---

• 위의 코드에서 anagrams 와 res 를 각각 키와 밸류값으로 가지는 딕셔너리로 합쳐서 사용하면 런타임이 줄어들 것이라 생각했다.

  class Solution:
      def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
          res = dict()
          for word in strs:
              key = ''.join(sorted(word))
              if key not in res:
                  res[key] = [word]
              else:
                  res[key].append(word)
  
          return res.values()

  
• 딕셔너리 자료형을 이용하니 속도가 빨라진 것을 확인할 수 있었다.

---

• 교재에 나온 코드

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

• collection.defaultdict(자료형) 은 딕셔너리에서 value값을 해당하는 자료형으로 설정해주는 유사 딕셔너리 자료형이다.