[Python/LeetCode] 49. Group Anagrams

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

 

입력 : 소문자 영어 단어들로 이루어진 문자열 배열(리스트) `strs`

출력 : `strs` 내의 groups of anagram으로 이루어진 2차원 리스트

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

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

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

---

직관 및 접근

당장 드는 생각은,

일단 strs를 순회를 돌거임 for문으로. 대신 첫 단어는 미리 어떤 리스트에 할당시켜둠.

그리고 그 다음 단어부터, 이게 이미 존재하는 리스트의 애너그램이면 그 리스트에 append하고,

그렇지 않으면 새로운 리스트를 만들어 거기에 그 단어를 넣음.

이를 반복하여 생긴 n개의 리스트를 하나의 리스트에 모두 append한 결과를 return함.

 

아니면... 딕셔너리 써가지고, 그 애너그램 그룹의 대표되는 단어(즉 첫 등장 단어)를 key로 하고

그 단어를 value에다가 리스트로 해서 생성

이후 등장하는 그 단어의 애너그램들을 value에 리스트에 계속 append

 

이 과정에서 리스트 컴프리헨션 쓸 수도 있을듯? 중복제거 안할거면.

---

여기서 더 어떻게 풀어야할지 모르겠어 정답 코드 확인함.

 

실전에서 저 풀이를 어떻게 떠올릴 수 있을까?

-> 일단 같은 애너그램 group일 경우, 하나의 리스트에 추가해야 된단 것으로부터, 딕셔너리를 써야 한단 것과 key에는 같은 그룹 안의 공통적인 게 들어가야 한단 걸 알 수 있음.

-> 따라서, key에다가 sorted()함수의 결과인 정렬된 놈을 대표격으로 사용할 수 있지 않을까 생각 가능.

-> 이후, list(dict.values())로 깔끔하게 리스트만 반환 가능.

-> 이 때, value에다가 list를 넣어야 하니까, append 메서드를 사용해야 함.

-> 이를 위해, defaultdist(list)를 사용해, 기본 빈 리스트 `[]`를 생성하게 함.

---

공부내용

* Anagram (애너그램)

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

- 애너그램은 원래의 모든 글자를 정확히 한 번만 사용하여 다른 단어나 구의 글자를 재배열하여 만든 단어 또는 구를 말합니다.

- ex. ` "ate","eat","tea" ` <- a group of anagram

 

* sorted() 

- 첫 매개변수(정렬 대상)으로 리스트, 문자열, 튜플, 딕셔너리 등 이터러블 객체를 받을 수 있지만,

- 정렬 대상이 뭐든간에, 결국 정렬된 리스트를 반환함.

- 즉, 문자열을 정렬하고 싶으면, 반환값을 `''.join()`을 이용해 문자열로 바꿔줘야함.

---

정답풀이(책)

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # 밑에서 append할 때, 기본 value인 '[]'에다가 append되도록 설정
        anagrams = collections.defaultdict(list)
        
        for word in strs:
                # 정렬하여 딕셔너리에 추가
                # key는 정렬된 놈으로 조회, value에 append할 땐 원본 놈으로
            anagrams[''.join(sorted(word))].append(word)
                # sorted(word) <- 리스트
                # ''.join(sorted(word)) <- 문자열
                # anagrams[''.join(sorted(word))] <- 딕셔너리의 value
                # anagrams[''.join(sorted(word))].append(word) <- 딕셔너리의 value에 append 적용
        return list(anagrams.values())

특별히 여기서 더 개선 가능한 건 없어보인다.

---

해당 글은 "파이썬 알고리즘 인터뷰(박상길)"을 공부한 내용과 책의 코드가 포함되어 있습니다.

https://github.com/onlybooks/python-algorithm-interview/tree/master