04_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.

내가 푼 것

-> 못품 ㅠㅠㅠㅠㅠ 주석으로 로직은 맞게 썼는데 함수를 뭘 써야하는지 도저히 생각이 안났음 ㅠㅠ 실제로도 모르는 거였음...그래도 풀 죽지말고 하자!

솔루션

import collections

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 list(anagrams.values())

알아둘 것은 다음과 같다.

1. join()
   기본적으로 리스트와 같은 iterable한 것들을 선형적으로 이어붙이는(concatenate) 함수. 여기서 prefix는 이어붙일 때 그 사이에 뭘 넣어서 할 것이냐를 지칭한다. 예컨대 어떤 리스트가 ['a', 'b', 'c']로 되어있을 때, prefix가 ''(=empty string)이면 'abc'가 되고, 'd'이면 'adbdc'로 합쳐지는 거다.
2. sorted() (vs sort())
   정렬 함수인데, 이건 좀 중요하고 동시에 헷갈리는 거라서 따로 쓴 포스틀 보자.
3. for 루프는 도대체 어떻게 돌아가는가?
   지금껏 딕셔너리의 key에 뭘 추가 시키는 건 dictionary[key] = 0 뭐 이런 것만 해봤지 저런 식으로 하는 건 한 번도 본적이 없다. 처음엔 그래서 이 부분 이해하는 게 시간이 걸렸다. 특히나 이게 어떻게 anagram들 끼리만 모으는지가 이해가 안 갔음...예시를 들어서 보니깐 훨씬 더 이해가 빨랐다. 과정은 다음과 같다.
   다음과 같은 리스트가 있다고 치자.

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

   for 루프의 첫번째 iteration (word = "eat"인 경우)는 다음과 같다.
   • sorted(word)에서 "eat"를 ['a', 'e', 't']로 정렬
   • ''.join(sorted(word))를 통해 정렬된 각 문자를 "aet"로 이어붙임.
   • anagrams["aet"].append("eat")가 anagrams에서 "aet"라는 key에다가 "eat"을 list로 이루어진 value에다가 추가시킨다. (최초에 angrams를 정의할 때 list가 되어있는 걸 상기하자. 그리고 알게된 사실 하나!! -> value를 리스트로 할 수 있따!!!!)
   • 이제 'anagrams'는 {'aet': ['eat']}과 같은 구조를 갖게 된다.
     두번째 iteration (word = "tea"인 경우)
   • 첫번째 iteration과 동일하다.
   • 이제 'anagrams'는 {'aet': ['eat', 'tea']}과 같은 구조를 갖게 된다.
     세번째 iteration (word = "tan"인 경우)
   • 첫번째랑 두번째랑 동일하게 돌아가는데, 정렬되었을 때 ['a', 'e', 't']가 아니라 ['a', 'n', 't']니깐 결국 "ant"란 새로운 key가 생기게 되고 이에 대한 리스트 형태의 value로서 "tea"가 추가가 된다.
   • 따라서 'anagrams'는 {'aet': ['eat', 'tea'], 'ant': ['tea']}와 같은 구조를 갖게 되는 거다!! 이렇게 anagram이 되는 것들 끼리 모으는 거다. (이 부분이 참 신기하게 느껴졌다 ㅋㅋ)
     이후 iteration도 동일한 방식으로 진행된다.
4. values()로 반환
   마지막 return에서 angrams을 이루는 단어들 끼리 출력을 해야하니깐 values()로 뽑은 다음 이를 list() 함수에 넣어 nested list 형태로 반환한다.

꽤나 많은 걸 배운 문제였음. 특히 저 for 루프 돌아가는 게 처음엔 도대체 왜????? 이러다가 이해하니깐 신기했다 정말..오늘도 직관을 얻어서 좋았다.

끝.