[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.

 

* anagram: 문자를 재배열하여 다른 뜻을 가진 단어로 바꾸는 것

 

Example:

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

 

 루프 안에서 입력 리스트의 값 하나를 정렬하고 미리 만들어놓은 딕셔너리에 key로 정렬된 값을 넣고 value로 정렬 전 값을 리스트 형식으로 넣어주는데 조건문을 통해 정렬된 값이 같다면 같은 value 리스트안에 추가하게 코드를 짰다. 그런 뒤 마지막엔 리턴 할 리스트를 만들어 그 리스트에 딕셔너리 값만 리스트로 던져주어 이중리스트 형태로 애너그램을 리턴해 주었다. 처음에 리스트 값을 정렬할 때 sorted()를 사용하였는데 이는 문자열을 정렬하여 순서대로 리스트에 담아주었다. 그래서 문자열을 다시 join()하여 담아 사용했다.

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        
        # distinguish using dictionary
        str_dic = {}
        
        for e in strs:
            temp = sorted(e)
            ordered_e = ''.join(temp)
            
        # below setence(line14) causes unhashable type 'list'!
        # Because sorted() make each letter to an element of list.
        # That's whay I use join method to make string again.
            
            if ordered_e not in str_dic:
                str_dic[ordered_e] = [e]
            else:
                str_dic[ordered_e].append(e)
                
        # take only values from dictionary
        answer = []
        
        for k, v in str_dic.items():
            answer.append(v)

        return answer

 

 풀이를 보니 디폴트를 생성해주는 defaultdic()을 선언하여 간결하게 문제를 풀이하였다. 존재하지 않는 key에 append하면 KeyError가 발생해 defaultdic()을 사용하는 것이 좋다고 한다.

import collections

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 list(anagrams.values())