[leetcode 49.python] 그룹 애너그램 (Group Anagrams) 풀이

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

Group Anagrams - LeetCode

---

문제

Given an array of strings strs, group the anagrams together. 

문자열 배열을 받아서, 애너그램으로 그룹핑하시오.

 

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"]]

---

문제 이해

애너그램으로 그룹핑하라고 ..? 어떻게 하라는 거지 싶었다.

위에 표시된 예시 1을 보고 애너그램은 뭔지 모르지만 '문자열을 재배열해서 동일한 문자열끼리 다시 그룹핑하라는 거구나!' 라고 이해했다.

 

추후 추가 - 출처

그렇다고 한다

---

문제 풀이

애너그램을 정렬하여 같은 값을 가졌는지 비교하기 위해 파이썬 정렬 문법을 찾아보았다.

	a = "eat"	b = "ate"	c = "tea"
정렬: sorted()	sorted(a) >>> ['a', 't', 'e']	sorted(b) >>> ['a', 't', 'e']	sorted(c) >>> ['a', 't', 'e']
공백없이 합치기: ".join()	".join(sorted(word)) > 'aet'	".join(sorted(word)) > 'aet'	".join(sorted(word)) > 'aet'

 

위와 같은 로직으로 결론적으로 값 'aet'가 나오는 것을 확인할 수 있었다. 

이후 같은 애너그램을 가진 원소들끼리 묶기 위해, 애너그램을 key, 원래 단어를 value로 하는 딕셔너리를 만든다.

 

이 때 딕셔너리에는, 존재하지 않는 key를 삽입할 경우 에러가 발생하는 문제가 생길 수 있다 > defaultdic을 통해 해결 가능 

 

1. 딕셔너리 key 값은 중복될 수 없기에 'ate'를 key값으로 설정하고,

2. for문을 통해 value에 정렬했을 때 'ate'가 되는 모든 문자를 

3. key가 'ate'인 value로 append()를 통해 담으면 됐다.

 

4. 정렬 값이 'ate'가 아닌 'tan', 'nat'은 'tan'을 key값으로, 'tan', 'nat'가 value값으로,

    'bat'는 'abt'가 key값이 되어 'bat'가 value값으로 들어간다.

 

5. for문을 돌린 결과 나오는 출력값 

defaultdict(<class 'list'>, {'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat'], 'abt': ['bat']})

 

6. 위의 값에서 단어들만 빼야하기 때문에, value값만 추출해주는 value()를 사용해서 값을 내주자.

return anagrams.values()
[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

 

---

문제 답

import collections
from typing import List
# collections? 파이썬의 내장모듈로 이 모듈에서는 defaultdic을 지원함
#key의 개수를 세어야 하는 상황이나, list나 set의 항목을 정리해야하는 상황에 적절

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # defaultdict : 존재하지 않는 key로 인한 에러 방지를 위해 사용 
        # 기본값 초기화 하지 않아도 자동으로 해주며 예외처리할 때 편하다.
        anagrams = collections.defaultdict(list)
        print(anagrams)

        for word in strs:
            # 정렬하여 딕셔너리에 추가 / 주어진 문자를 알파벳순으로 정렬하여 같은 애너그램을 key로 dic에 저장한다.
            anagrams[''.join(sorted(word))].append(word)
        print(anagrams)

        return list(anagrams.values()) 

---

마치며 

내 개발자 인생 첫 알고리즘 문제와 첫 파이썬이라 ,, 풀면서 파이썬 문법도 찾아보면서 푸느라고 시간이 꽤 걸렸다.

그래도 잘 이해하면서 푼 것 같아서 뿌듯하다 ! 앞으로 더 열심히 하자!