LeetCode [49]: Group Anagrams

📌 LeetCode [49]: Group Anagrams

🔗 문제 링크

---

문제 설명 📄

문자열 배열 strs가 주어질 때, 애너그램(Anagram) 관계인 문자열들을 그룹으로 묶는 문제입니다.

• 애너그램: 단어를 구성하는 문자들이 동일하지만 순서가 다른 경우.
• 각 그룹은 문자열 배열로 반환하며, 그룹 내 문자열의 순서는 중요하지 않습니다.

---

문제 접근 방식 📋

1. 문자 빈도 기반 분류:
   • 애너그램은 단어를 구성하는 문자의 종류와 개수가 동일합니다.
   • 따라서 collections.Counter를 사용해 문자열의 문자 빈도를 계산하고, 이를 기반으로 그룹을 생성할 수 있습니다.
2. Key로 frozenset 사용:
   • frozenset은 변경 불가능한 자료형으로, Counter의 (문자, 빈도)를 키로 사용하여 그룹화할 수 있습니다.
3. 효율성:
   • 문자열마다 Counter를 계산해야 하므로, 시간 복잡도는 입력 문자열의 문자 수에 비례합니다.

---

Solution 💻

from collections import Counter, defaultdict

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        pattern = defaultdict(list)

        for s in strs:
            count = frozenset(Counter(s).items())
            pattern[count].append(s)

        return [group for group in pattern.values()]

시간 복잡도 분석 ⏲️

1. Counter(s) 계산:
   • 각 문자열 s의 문자 빈도를 계산하는 데 (O(L)), 여기서 (L)은 문자열의 길이입니다.
2. frozenset 변환:
   • Counter의 키-값 쌍을 frozenset으로 변환하는 데 (O(L)).
3. 전체 복잡도:
   • 입력 배열의 문자열 개수를 (n), 각 문자열의 평균 길이를 (L)이라고 하면:
     • 총 시간 복잡도는 (O(n \times L)).

공간 복잡도 분석 🗄️

• Counter와 frozenset:
  • 각 문자열마다 문자 빈도 저장에 (O(L)).
• defaultdict:
  • 최악의 경우 모든 문자열이 다른 그룹에 속한다면 (O(n \times L)).
• 총 공간 복잡도: (O(n \times L)).

---

리팩토링 🛠️

개선된 코드 (정렬 기반)

애너그램은 문자를 정렬하면 동일한 결과를 갖습니다. 이를 활용해 더 간결한 코드로 작성할 수 있습니다.

from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        pattern = defaultdict(list)

        for s in strs:
            sorted_key = ''.join(sorted(s))
            pattern[sorted_key].append(s)

        return [group for group in pattern.values()]

리팩토링 코드의 장점

1. 간결한 구현:
   • sorted(s)로 애너그램 키를 생성.
   • Counter 기반보다 직관적이고 코드 길이가 짧음.
2. 시간 복잡도:
   • 정렬 기반의 시간 복잡도는 (O(L \log L))이며, 전체 복잡도는 (O(n \times L \log L))입니다.
   • 작은 문자열에서는 이 방식이 더 빠르게 작동할 가능성이 큽니다.

Counter 기반 코드

• 시간 복잡도: (O(n \times L))
• 장점: 문자의 정렬이 필요 없으므로, 더 큰 입력(긴 문자열)에서 효율적.

정렬 기반 코드

• 시간 복잡도: (O(n \times L \log L))
• 장점: 직관적이고 간결한 코드.

애너그램 문제에서 문자열 길이가 짧다면 정렬 기반 방식이, 길다면 Counter 기반 방식이 더 유리합니다.