리트코드 - Group Anagrams

 

문제

https://leetcode.com/explore/interview/card/top-interview-questions-medium/103/array-and-strings/778/

 

문제 설명

문자열 배열 strs가 주어질 때, 애너그램(anagram) 들을 그룹으로 묶어서 반환하세요. 반환되는 결과의 순서는 상관없습니다.

애너그램이란?

• 애너그램은 주어진 문자열의 문자를 재배열하여 다른 문자열을 만들 수 있는 경우를 말합니다.
• 예를 들어:
  • "eat", "tea", "ate"는 서로 애너그램입니다.
  • "tan"과 "nat"도 서로 애너그램입니다.
  • "bat"는 애너그램이 없는 단독 그룹입니다.

 

예제

입력 및 출력 예시

예제 1:

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

예제 2:

• 입력: strs = [""]
• 출력: [[""]]

예제 3:

• 입력: strs = ["a"]
• 출력: [["a"]]

 

---

 

풀이

1. 정렬을 활용한 그룹화

 

• 문자열의 문자를 오름차순으로 정렬하면 동일한 애너그램들은 같은 형태의 문자열로 변환됩니다.
• 예:
  • "eat" → "aet"
  • "tea" → "aet"
  • "tan" → "ant"
• 이를 활용해 정렬된 문자열을 키(key)로 사용하여 같은 애너그램 그룹을 저장합니다.

2. 딕셔너리 활용

• 키는 정렬된 문자열, 값은 해당 애너그램에 속하는 원래 문자열들의 리스트로 딕셔너리를 구성합니다.

3. 결과 반환

• 딕셔너리에 저장된 값들(리스트)만 반환합니다.

 

---

 

코드

from collections import defaultdict

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