[LeetCode | Python] 49. Group Anagrams

anagram은 일단 sort 후 비교를 떠올리자!

 

풀이1: 리스트 활용

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        result = []
        visited = [False] * len(strs)

        for i in range(len(strs)):
            if visited[i]:
                continue
            tmp = []
            tmp.append(strs[i])
            visited[i] = True
            for j in range(len(strs)):
                if sorted(strs[i]) == sorted(strs[j]) and i != j:
                    tmp.append(strs[j])
                    visited[j] = True

            result.append(tmp)
        
        return result

리스트 활용 풀이가 익숙해서 일단 리스트부터 손이 간다.

위 풀이는 neetcode에선 맞지만, leetcode에선 시간 초과가 났다.

for문 두 개이니 O(N^2), sorted에서 O(klogk)이니  O(N^2 * klogk)의 시간 복잡도를 갖는다.

 

풀이2: defaultdict 활용

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

        res = defaultdict(list)
        for s in strs:
            sortedS = ''.join(sorted(s))
            res[sortedS].append(s)
        return list(res.values())

defaultdict(list) : value가 리스트인 딕셔너리 생성, key는 자동 생성

for문 두번 돌리면서 비교할 필요 없이, 한번만 순회하며 딕셔너리에 추가해주면 된다.

sorted 하면 똑같이 나오니 그걸 key로 사용하면 된다.

res.values()로 밸류만 뽑아주고

def 선언의 return 타입에 맞춰 list로 캐스팅해준 후 리턴해준다.

시간 복잡도는 O(m * nlogn)