그룹 애너그램 문제

 

 

 

문제는 간단하다. 포함된 알파벳 구성이 동일한 것끼리 리스트로 묶어주면 된다. 어렵지 않은 문제이다. 이 문제가 애너그램 단위로 그룹핑하는 문제이다.

 

아래의 코드는 정답을 맞추기 위해서 짰던 코드이다. 가장 핵심적인 것만 요약해보면, input 으로 들어오는 strs 속의 모든 단어들에게 정렬 시킨 단어와 pairwise 하게 짝을 지어준다. 그게 아래의  answer 인데 [('abc', 'abc'),('bca', 'abc'), ('cba', 'abc')] 이런식으로 쌍을 만들어주고, answer_d 딕셔너리를 만들고, 원래 단어의 정렬한 것인 key 값을 비교해보면서 동일한 key 값인 경우에는 append 를 시켜주는 식으로 진행하였다.

    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        answer = []
        for i in strs:
            answer.append((i,''.join(sorted(i))))

        answer_d = {}
        for val, key in answer:
            if key not in answer_d.keys():
                answer_d[key] = [val]
            else:
                answer_d[key].append(val)

        return [i for i in answer_d.values()]

 

 

다소 복잡했던 코드는 좀 더 깔끔하게 요약을 다 해주셨다. 위의 코드에서는 key 가 존재하는지 묻는 if 문이 계속 반복되게 된다. 하지만 collections 모듈에 defaultdict는 key가 없는 경우 이미 설정된 타입으로 key: value 를 꾸려준다. 불필요한 if 문을 완벽하게 제거했을 뿐만 아니라 sorted 부분도 함께 적용했기 때문에 계산복잡도 n 으로 끝났다.

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

 

 

defaultdict 버릇을 들이자.!

 

 

 

ref) 파이썬 알고리즘 인터뷰

leetcode.com/problems/group-anagrams/submissions/