• 문제 : https://leetcode.com/problems/group-anagrams/

답안

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        def get_hash(string):
            hash_sum = 0
            for char in string:
                hash_sum += hash(char)
            return hash_sum

        strs_with_hash = [(word, get_hash(word)) for word in strs]
        strs_sorted = sorted(strs_with_hash, key=lambda x: x[1])

        result = []
        hash_val = None
        for tup in strs_sorted:
            if hash_val != tup[1]:
                result.append([tup[0]])
                hash_val = tup[1]
            elif hash_val == tup[1]:
                result[-1].extend([tup[0]])

        return result

같은 문자열의 재배치 결과인 애너그램을 찾는 문제기 때문에, 각 문자를 hash값으로 만든 다음 더해주면 같은 애너그램끼리는 같은 결과가 나올 것으로 생각했다. 그러나 hash값을 구하나, 문자열을 정렬하나 사실 여기서는 전체 문자열 길이가 길지 않기 때문에 시간 차이는 크지 않을 것이다(`word.length<100`).

따라서 모범 답안은 다음과 같다.

from typing import Collection


class Solution:
    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()

defaultdict 하나만으로 엄청 깔끔하게 해결 가능하다.

첫번째 열이 모범답안, 두번째 열이 내 답안이다. 리트코드 테이스케이스가 완벽하지 않아서 그런지는 몰라도 둘 다 시간이나 메모리 차이가 크지 않다.