LEETCODE - Group anagrams

Coaspe·2021년 5월 3일
0
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

profile
https://github.com/Coaspe

0개의 댓글