Group Anagrams

애너그램으로 그룹화하기

문제 이해

문제를 해석해 보자.

문자열 배열 strs가 주어진다.

문자열 배열에서 anagrams 끼리 그룹화하여 반환하라.

반환할 때 문자열의 순서는 상관 없다.

문자열을 그룹화하라는 데, anagrams가 뭘까?

Anagrams

An anagram is a word or phrase formed by rearranging the letters of adifferent word or phrase, using all the original letters exactly once.

문제에 anagrams의 정의가 나와있다.

한국어로 번역하면, anagram은 원래의 모든 글자를 정확히 한 번 사용하여 만든 단어 또는 구절을 의미한다.

예를 들어, listen과 silent는 모두 listen의 문자를 재배열하여 만들 수 있는 단어이므로 anagram 그룹으로 묶을 수 있다.

문제 조건

문자열 배열에 있는 문자열들은 모두 소문자로 구성되어 있다고 나와있다. 따라서 대소문자를 구분하지 않고 anagrams 그룹으로 묶어주면 될 것 같다.

문제 풀이

모든 경우의 수를 고려

어떻게 하면 anagram 관계에 있는지 확인할 수 있을까? 문자열을 재배열할 수 있는 모든 경우의 수를 고려하여 비교하면 해결 할 수 있겠지만, 문자열의 길이가 길어지면 비교 횟수가 기하급수적으로 증가할 것이다.

문자열의 최대 길이가 100이므로, 만약 길이가 100인 문자열이 있다면 100! 번의 비교가 필요하다. 이건 말이 안된다. 🥲

문자열 정렬

문자열을 정렬하여 비교하는 방법은 어떨까?

같은 anagram 그룹에 있는 문자열들은 정렬했을 때 모두 같은 문자열을 가리킬 것이다. 예를 들어 abc, acb, bac, bca, cab, cba는 모두 정렬했을 때 같은 abc 가 된다.

효율적인 정렬 알고리즘은 시간 복잡도가 보통 O(n log n) 이다. 따라서 제한 조건을 고려하더라도 충분히 문제를 해결 할 수 있을 것 같다.

그럼 이 방법으로 코드를 작성해 보자.

코드 작성

group-anagrams.py

from collections import defaultdict
 
class Solution:
    def _generate_sorted_key(self, word: str) -> str:
        # 문자열을 정렬하여 키 생성
        return "".join(sorted(word))
 
    def groupAnagrams(self, words: list[str]) -> list[list[str]]:
        # 애너그램을 그룹화하기 위한 해시맵 초기화
        anagram_groups = defaultdict(list)
 
        # 각 단어를 순회하면서 애너그램 그룹화
        for word in words:
            # 정렬된 문자열을 키로 사용
            sorted_key = self._generate_sorted_key(word)
            anagram_groups[sorted_key].append(word)
 
        # 그룹화된 애너그램 리스트 반환
        return list(anagram_groups.values())

리스트를 value로 갖는 딕셔너리를 사용하여 애너그램 그룹을 관리하고, 정렬된 문자열을 key로 사용하여 애너그램 그룹을 분류한다.

사실 특별한 알고리즘이 필요하지 않아서 설명할 내용은 없다.

추가로, 굳이 join 메서드를 이용하여 문자열을 키로 할 필요없이 그냥 정렬된 결과를 tuple로 변환하여 키로 사용해도 된다. 그러면 _generate_sorted_key 메서드를 아래와 같이 작성할 수도 있다.

def _generate_sorted_key(self, word: str):
    return tuple(sorted(word))

마무리

정렬을 이용한 그룹화 방법을 생각해 내기만 하면 쉽게 풀 수 있는 문제였다.

참고&공부 자료

파이썬 알고리즘 인터뷰