49. Group Anagrams

버전1

strs = ['eat', 'tea', 'tan', 'ate', 'nat', 'bat']

class Solution:
    def groupAnagrams(self, strs):

        result = []
        
        for word in strs:
            new_word = ''.join(sorted(word))

            added = 0
            # 맨 처음에 빈 리스트일때 추가
            if not result:
                result.append([word])
                added = 1
            else:
                for list in result:
                    # 리스트가 차있고 애너그램이면 추가해줌
                    if ''.join(sorted(list[0])) == new_word:
                        list.append(word)
                        added = 1
                        break

            # 애너그램인 단어가 없으면 리스트에 추가
            if added == 0:
                result.append([word])
        
        return result
                
print(Solution.mostCommonWord(Solution, strs))

했는데 시간 초과 나옴.

책 정답

import collections

class Solution:
    def groupAnagrams(self, strs):

        # 리스트를 값으로 하는 딕셔너리 생성
        # https://docs.python.org/3/library/collections.html#collections.defaultdict.default_factory
        anagrams = collections.defaultdict(list)

        for word in strs:
            # sorted(word)로 개별 단어를 문자로 분리해서 정렬하고 join으로 다시 문자열로 합친거를 키로 사용함
            # append로 이제 그 합친거를 딕셔너리의 value(리스트)에 집어 넣음
            anagrams["".join(sorted(word))].append(word)
            
        # 딕셔너리의 value에 다 들어있으니 value만 리스트로 묶어서 리턴해줌.
        return list(anagrams.values())

print(Solution.groupAnagrams(Solution, strs))

출처