import collections
def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
anagrams = collections.defaultdict(list)
for word in strs:
anagrams[''.join(sorted(word))].append(word)
return anagrams.values()
# sorted(문자열,key)하면 배열로 반환해준다."eat" -> ['a','e','t']
# sorted(문자의 배열)하면 문자들을 정렬한다. ["eat","tea","tan","ate","nat","bat"] -> ['ate', 'bat', 'eat', 'nat', 'tan', 'tea']
병합 정렬
은 일정하게 O(nlogn)
의 안정적인 성능을 보이며 안정 정렬
이라는 점에서 많이 선호된다.
그렇다면 파이썬의 sorted()
는 어떤 알고리즘 일까?
파이썬의 정렬은 Timsort
를 사용한다.
데이터가 엉망으로 뒤죽박죽 섞여 있는 일은 실제로 거의 일어나지 않을 것이라 가정하고 삽입 정렬
과 병합 정렬
을 휴리스틱하게 사용하는 정렬 알고리즘이다.
퀵 nlogn nlogn n^2
병합 nlogn nlogn nlogn
팀소트 n nlogn nlogn