49. Group Anagrams

애너그램(Anagram): 일반적으로 모든 원래 문자를 한 번만 사용하여 다른 단어 또는 구의 문자를 재배열하여 형성된 단어 또는 구이다.

이 애너그램의 집합을 구하는 문제.

Solution

1. strs 배열의 한 문자를 정렬한다.
2. 정렬한 뒤 정렬한 문자를 key 값으로, 원래 문자를 value 값으로 저장한다.
3. strs 배열을 비우고 딕셔너리의 value 값들만 넣어주고 반환한다.

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        dic = {}
        for i in range(len(strs)): # O(n)
            temp = ''.join(sorted(strs[i])) # O(nlogn)
            if temp not in dic: dic[temp] = [] # O(1)
            dic[temp].append(strs[i]) # O(1)
        strs[:] = []
        for i in dic: # O(n)
            strs.append(dic[i])
        return strs

시간 복잡도

1. O(nlogn)*O(n) 반복문이므로
2. O(1)
3. O(n)

총 시간 복잡도는 O(N^2logN)+O(n), 즉 O(N^2logN)이다...
완전 최악아님?

다른 풀이도 더 찾아봐야지.