리트코드 LeetCode - 49.Group Anagrams (Python)

오늘 풀어본 문제는 다음과 같다.

LeetCode 49.Group Anagrams
문자 배열을 받아, 애너그럼 단위로 그룹핑하라.
입력:
["eat","tea","tan","ate","nat","bat"]

[문제풀이]

여기서 애너그램이란, 문자를 재배열하여 다른 뜻을 가진 단어로 바꾸는 것을 말한다.
예를 들어, eat의 구성요소는 'a','e','t' 이고 ate의 구성요소는 'a','e','t'로 이 둘은 그룹핑되어야 한다.
그래서 문자를 보고 sorted() 와 파이썬의 dictionary를 사용하였다.

strs = ["eat","tea","tan","ate","nat","bat"]
anagrams = collections.defaultdict(list)

입력들을 for문으로 돌면서, sorted() 한 뒤 dictionary에 Join 시키면 그 단어의 구성요소가 어떤 순서로 되어있던지 상관없기 때문이다.

print(sorted(word))

실제로 입력은 'eat, ate, tea' 등 구성요소의 순서가 다르지만 sorted()를 이용하면 다음과 같이 모두 a,e,t 의 순서로 정렬된다.
따라서, 위 출력을 key로 하고 단어의 원형을 value로 join 시켜주었다.

for word in strs:
    anagrams[''.join(sorted(word))].append(word)

그리고, dictionary의 value만 출력해주면 쉽게 해결할 수 있다.

[전체 코드]

import collections

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        
            anagrams = collections.defaultdict(list)

            for word in strs:
                print(sorted(word))
                anagrams[''.join(sorted(word))].append(word)

            return list(anagrams.values())

[이 문제 풀면서 공부한 점]

Python의 dictionary?:
Python의 dictionary 내부는 키/값 해시 테이블로 구성되어있다.

defaultdict()로 선언한 이유 :
sorted()로 정렬한 값을 key로 저장하는데, 만약 존재하지 않는 key를
삽입하려할 경우 KeyError가 발생하기 때문이다.