[LeetCode 해석 및 풀이] 49. Group Anagrams

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가 주어지면, 같은 아나그램을 묶으세요. 답의 순서는 상관 없습니다.

 

아나그램이란 일반적으로 모든 원래 문자를 정확히 한 번씩 사용하여 다른 단어나 구문의 문자를 재배열하여 형성된 단어나 구문입니다.

 

제한조건

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters.

 

입출력 예

입력	출력
strs = ["eat","tea","tan","ate","nat","bat"]	[["bat"],["nat","tan"],["ate","eat","tea"]]
strs = [""]	[[""]]
strs = ["a"]	[["a"]]

 

 

해답 및 해설

파이썬 (Python)

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        def hash_function(word:str):
            alphabet_list = [0]*26
            for c in word:
                alphabet_list[ord(c)-97] += 1

            result = ''
            for i, value in enumerate(alphabet_list):
                if value == 0: continue
                result += chr(i+97) + str(value)
            
            return result
        
        group_dict = {}
        for word in strs:
            key = hash_function(word)

            value_list = group_dict.get(key, [])
            value_list.append(word)

            group_dict[key] = value_list
        
        return group_dict.values()

우선 DAT 자료형을 이용하여 각 단어들에서 알파벳 수를 세어 key를 만들어주었다. 이 과정에서 같은 아나그램은 같은 key를 가지게 된다. 그 후 딕셔너리에 넣어 같은 아나그램들을 모아준다. 이후 value값을 return 해준다.

 

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        result = defaultdict(list)
        
        for str in strs:
            count = [0] * 26
            for char in str:
                count[ord(char) - ord('a')] += 1
            result[tuple(count)].append(str)

        return result.values()

 나랑 같은 아이디어인데, defaultdict을 사용하여 초기화를 시켜주고 tuple 자체를 key로 넣어버린 해법이 있었다.

 

class Solution:
    def groupAnagrams(self, strs):
        anagram_map = defaultdict(list)
        
        for word in strs:
            sorted_word = ''.join(sorted(word))
            anagram_map[sorted_word].append(word)
        
        return list(anagram_map.values())

이 외에도 단어를 정렬하여 key로 쓴 경우가 있었다. 속도가 위 방식보다 느릴것으로 예상했으나, 더 빨랐다. 아마 단어 길이가 짧아서 그러지 않을까 싶다.