Group Anagrams

LeetCode의 Group Anagrams 문제다.

Group Anagrams - LeetCode

주어진 문자열들에 대하여 애너그램에 해당하는 단어끼리 묶어서 리스트로 반환하는 것이 목적인데 처음에 생각한 것은 어차피 애너그램은 글자가 뒤죽박죽 섞여있더라도 결국 문자의 개수는 동일하기 때문에 이전 포스트에서 활용한 Counter 클래스를 이용하여 각 문자 별 빈도를 계산, 동일 여부로 계산하는 방법이었다.

import collections


class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        if len(strs) < 2:
            return [strs]
        
        anagrams = [[strs.pop()]]
        
        for word in strs:
            is_unique_anagram = False
            for anagram in anagrams:
                anagram_word = anagram[0]
                
                if len(word) != len(anagram_word):
                    continue
                
                anagram_word_counter = collections.Counter(anagram_word)
                current_word_counter = collections.Counter(word)
                
                if anagram_word_counter == current_word_counter:
                    anagram.append(word)
                    is_unique_anagram = True
                    break
                    
            if is_unique_anagram is False:
                anagrams.append([word])
            
        return anagrams

이 코드는 대부분의 테스트 케이스를 통과했지만 112번째 테스트 케이스에서 시간 초과 문제가 발생하였는데 테스트 케이스의 크기를 보니 시간 초과가 발생할만했다. 약 11만 자의 텍스트였기 때문에 이 Counter 클래스를 활용하는 방법에서 좀 시간이 많이 소모된 것 같은데 이를 어떻게 해결할 수 있을까? 책에서는 파이썬의 sorted 메서드를 활용한 방법을 제시하고 있었다.

>>> l = ['b', 'c', 'a', 'd']
>>> sorted(l)
['a', 'b', 'c', 'd']
>>> l
['b', 'c', 'a', 'd']
>>> s = "bcad"
>>> sorted(s)
['a', 'b', 'c', 'd']
>>> s
'bcad'

리스트의 sort 메서드와는 달리 sorted 메서드는 매개변수로 iterable 객체를 받아서 정렬된 객체를 담은 리스트를 반환한다. 이 메서드는 위처럼 문자열에도 활용할 수 있는데 평소에 문자열에 포함된 문자를 순회하는 것이 가능했던 것을 생각해보면 문자열 역시 iterable 객체라고 생각할 수 있다. 그렇다면 이것을 어떻게 활용할 수 있을까? 이는 애너그램인 문자열은 sorted로 정렬하면 결국 같은 값을 가진 리스트로 반환되기 때문에 이를 비교하여 애너그램 여부를 확인할 수 있는 것이다.

>>> sorted("radio")
['a', 'd', 'i', 'o', 'r']
>>> sorted("dorai")
['a', 'd', 'i', 'o', 'r']

위처럼 같은 애너그램 문자열인 "radio"와 "dorai"를 sorted 메서드로 적용했을 때 같은 결과가 나오는 것을 볼 수 있다. 이를 활용하여 이 ['a', 'd', 'i', 'o', 'r'] 리스트 객체를 키로 가지는 사전 자료구조를 활용하여 해당 객체와 동일한 애너그램 문자를 값으로 넣어주는 방식으로 구현할 수 있다. 즉 모든 단어들을 sorted 메서드로 정렬하여 문자들의 리스트를 얻고 이를 키로 사용하는 것이다.

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

이전 포스트에서 활용했던 defaultdict 클래스를 사용하여 기본값을 지정해줘서 해당 키가 존재하는지 확인하는 번거로운 과정을 줄일 수 있었다. 위의 코드에서는 sorted 메서드로 정렬한 문자들을 문자열로 합쳐서 키로 사용하여 원본 문자열, 즉 애너그램 단어들을 리스트에 추가하는 것을 볼 수 있다.

 

 

파이썬에서 자주 사용하게 될 정렬 메서드인 sorted와 sort를 헷갈리지 않도록 하자. 전자는 정렬 조건들을 매개변수로 넘길 수도 있는 내장(built-in) 메서드며 후자는 리스트 객체에서 사용하는 정렬 메서드다. 가끔 익숙하진 않지만 사전 객체에 대해서도 인덱싱([])을 사용할 수 있다는 것을 잊지 말자.