[LeetCode] 49. Group Anagrams

- Problem

49. Group Anagrams

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

Input: strs = [""]
Output: [[""]]

Example 3:

Input: strs = ["a"]
Output: [["a"]]

Constraints:

• 1 <= strs.length <= 10^4
• 0 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters.

anagram인 것들끼리 묶는 문제이다.

anagram

단어나 문장을 구성하고 있는 문자의 순서를 바꾸어 다른 단어나 문장을 만드는 것

- 내 풀이

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

딕셔너리를 활용한 풀이이다.
주어진 배열 strs의 원소들을 알파벳 순서로 sort하여 키 값으로 활용하였다.
예를 들면, strs = ["eat","tea","tan","ate","nat","bat"]이 주어졌을 때, 차례대로 aet, aet, ant, aet, ant, abt 가 출력될 것이다

즉, 알파벳 순서로 정렬된 각각의 문자열 원소가 키가 되고, 그 키의 anagram에 해당하는 배열 strs의 원소 s를 value로 갖게 되는 것이다.

- 결과

unhashable type "list"

다른 사람의 풀이를 보던 중 내가 키 값으로 사용한 "".join(sorted(s) 가 아닌 tuple(sorted(s))와 같은 형태로 묶어둔 것을 보았다.

sorted(s)를 키 값으로 사용할 수 있지 않을까? 라는 의문을 가질 수도 있다.
그러나, 딕셔너리의 키 값으로 sorted(s)를 사용하게 된다면 unhashabe type "list"와 같은 에러를 마주치게 된다.

이유는 다음과 같다.
set이나 딕셔너리의 key는 해시할 수 있는 immutable이여야 한다.
tuple의 경우 한 번 정의된다면 데이터의 추가나 삭제가 불가능한 immutable type이다. 반면에 list는 잘 알다시피 정의된 이후에도 데이터의 추가나 삭제 등이 자유롭다.