문자열 조작 5 - Group Anagrams

49. Group Anagrams

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

My Answer 1: Accepted (Runtime: 96 ms - 80.15% / Memory Usage: 18.2 MB - 34.25%)

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        dic = collections.defaultdict(list)
        for i in range(len(strs)):
            s = str(sorted(strs[i]))
            dic[s].append(strs[i])
        
        return dic.values()

딕셔너리 key 값으로 정렬한 문자열을, value 값으로 원래 문자열을 저장

마지막엔 value 값들만 return

sorted => 리스트를 반환

ex) sorted("cba") = ["a", "b", "c"]

s = sorted(strs[i]) 라고 했을 때,
str(s) => "["a", "b", "c"]" 이 되므로
''.join(s) => "abc" 을 사용하자!

sorted: key 값을 지정한 정렬도 가능

• 문자열의 길이를 기준으로 정렬

sorted(s, key=len)

• 첫 문자 & 마지막 문자를 기준으로 정렬 - 1

def fn(s):
    return s[0], s[-1]
sorted(s, key=fn)

• 첫 문자 & 마지막 문자를 기준으로 정렬 - 2
  => lambda 를 이용하면 함수를 따로 만들지 않아도 됨

sorted(s, key=lambda s: (s[0], s[-1]))

팀소트(Timsort) => 파이썬의 sort(), sorted()

• 삽입 정렬과 병합 정렬을 휴리스틱하게 적절히 조합해 사용하는 정렬 알고리즘
• 실제 데이터는 대부분 이미 정렬되어 있을 것이다라는 가정을 기반으로 설계
• 가급적 sort 내장 함수를 사용하는 편이 가장 빠르다
• 최선: O(n) | 평균: O(n log n) | 최악: O(n log n)