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

들어가며

본 포스팅은 <파이썬 알고리즘 인터뷰> 책에서 다룬 리트코드 문제들을 다루고 있습니다. 

문제들은 모두 리트코드에서 출제된 문제들이며, 문제 풀이의 많은 부분을 책의 힌트와 해설을 참고하였습니다. 

 

포스팅되는 모든 문제들의 목록과 풀이는 파이썬 알고리즘 인터뷰에서 제공하는 깃허브에서 확인하실 수 있습니다.

 

---

문제

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

문자열을 받아 애너그램 단위로 그루핑하라.

 

애너그램(anagram)?
단어나 문장을 구성하고 있는 문자의 순서를 바꾸어 다른 단어나 문장을 만드는 놀이이다.
출처 - 위키백과

 

입출력 예시

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

 

생각과정

주어진 배열을 애너그램 단위로 묶는다는 건 각 단어를 알파벳 단위로 쪼개었을 때 알파벳의 종류과 개수가 일치한다는 걸 의미한다.

따라서, 배열의 각 단어를 알파벳 단위로 쪼갠다음 정렬해서 일치하는 단어가 있다면 하나의 리스트로 합치면 된다.

 

각 단어를 나눠서 정렬한 후 출력까진 했지만, 그 다음에 비교하는 코드를 짜려고 하니 시간이 너무 많이 소요되어서 힌트와 다른 사람의 코드를 보기로 했다.

 

풀이

다른 사람의 풀이코드를 보자.

 

출처 - 항해99 팀원 장경태님의 블로그

def groupAnagrams(strs):
    result = {} 
    for word in strs: 
        test = "".join(sorted(word))         
        if test not in result: 
            result[test] =list() 
            result[test].append(word) 
        else: 
            result[test].append(word) 
        result[test].sort()
    return list(sorted(result.values(),key=len))

딕셔너리를 생성한 후, for문을 사용해서 정렬된 한 단어를 test에 집어넣는다.

조건문을 이용해서 딕셔너리인 result에 없으면 새롭게 list를 만들어서 집어넣고, 있으면 list를 생성하지 않고 바로 집어넣는다.

최종적으로 result를 정렬한 후에 values를 리턴하는 코드이다. 

 

왜 딕셔너리를 이용해야하는 지는 이해가 되지 않아서 이 부분은 다른 사람들에게 조언을 구한 후 다시 작성하겠다.

 

아무튼 이번에는 해설지의 풀이코드를 보자.

anagram = collections.defaultdict(list)

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

return list(anagram.values())

해설지에서는 collections 라이브러리의 defaultdict() 함수를 사용하였다.

 

defaultdict()는 유사 딕셔너리로, 간단하게 설명하자면 기본 딕셔너리는 key와 value값을 지정해주어야만 하는데, defaultdict는 생성자로 기본값을 생성해주는 함수를 넘기면, 모든 key에 대해서 value가 없는 경우 자동으로 생성자의 인자로 넘어온 함수를 호출하여 그 결과값으로 설정해준다. 

 

다시 코드로 돌아가보면,

 

생성한 딕셔너리를 anagram에 담은 후, for문을 이용하여 주어진 문자열에서 단어를 하나씩 꺼내준다. 꺼내진 단어를 sorted()함수로 정렬해주면 쪼개진 알파벳 하나하나가 리턴되는데, 이것들을 join()함수로 합쳐준 후, anagram의 키로 지정. 다시 순서대로 딕셔너리에 append해준다. 

 

이 과정을 거치면 각 key와 일치하는 단어들은 한 뭉탱이로 저장될텐데, 이것들을 다시 list화 시켜서 return시켜주면 완성!

 

---

마치며

내 첫 알고리즘 문제... 앞으로 더 잘 할 수 있겠지.

 

나중에 이 글을 다시 보면서 미소지을 나를 위해서 열심히 하자!

 

---

참고

[파이썬] 사전의 기본값 처리 (dict.setdefault / collections.defaultdict)