[LeetCode] 49. Group Anagrams (문자열 조작)

문제

https://leetcode.com/problems/group-anagrams/

Group Anagrams - LeetCode

애너그램끼리 함께 묶어보자. 정답에서 애너그램과 단어의 순서는 상관하지 않는다.

애너그램 그룹은 같은 문자를 가졌지만 다른 의미를 가진다.

 

내 풀이

시간 : 156ms

1. 같은 애너그램 그룹에 속하는지 파악하기 위해 strs 안의 단어를 정렬하였다.

2. 정렬했을 때 같은 단어들의 조합으로 되어있으면 같은 애너그램 그룹에 속하므로, 단어들을 리스트로 초기화한 defaultdict에 넣었다.

3. defaultdict의 value를 반환하였다.

 

from collections import defaultdict

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

 

다른 풀이

시간 : 143ms

내 풀이와 방법은 동일한데, 좀 더 간결하게 만들었다.

나는 먼저 단어를 정렬한 배열을 만들었다. 그 후 defaultdict에 넣는 과정을 진행하였다. 그러나 이 풀이는 defaultdict에 넣을 때 단어를 정렬하였다.

이렇게 하면 시간이 아주 조금 더 빠르게 된다.

 

from collections import defaultdict

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()