leetcode 49. Group Anagrams 리트코드 49. 그룹 애너그램 문제 풀이

<파이썬 알고리즘 인터뷰> 책에서 다룬 리트코드 문제들을 풀이한 포스팅이다.

 

문제는 모두 리트코드에 출제된 문제들이며, 직접 풀었지만, 책에서 주는 힌트와 풀이 과정들을 참고한 경우가 많다.

이곳은  정리한 책에 나온 문제에 대한 목록과 해설을 정리한 공식 깃허브 페이지 이며, 

다음 포스팅은 내가 푼 <파이썬 알고리즘 인터뷰> 문제 풀이 목록을 정리해 놓았다.

 

문제

그룹 애너그램

 

입력: 문자열로 된 리스트

출력: 문자열로 된 리스트의 리스트

 

문제 요약: 애너그램은 문자를 재배열하여 다른 뜻을 가진 단어로 바꾸는 것을 뜻한다고 한다. (출처: 파이썬 알고리즘 인터뷰) 예를 들어 'eat' 과 'tea' 와 같은 것이다.

                 

유의 사항: strs[i].length == 0 인 경우도 포함된다. 즉, 아무것도 없는 빈 원소까지 고려해서 짜야 한다.

 

생각 과정

같은 애너그램 단위로 묶으라는 것은 결국 단어 안의 알파벳 종류와 갯수가 같은 단어끼리 묶어서 출력하라는 뜻 같다.

즉, 예시처럼 'eat', 'tea', 'ate' 세 단어는 모두 'a' 1개, 'e' 1개, 't' 1개로 구성되어 있어서 같은 그룹으로 묶을 수 있다.

 

1. 입력된 strs의 원소인 단어들을 알파벳 별로 쪼개고, 정렬시키면, 같은 알파벳으로 구성된 애너그램들은 똑같은 결과물이 나온다.

2. 같은 애너그램을 가진 원소들끼리 묶어야 하므로, 애너그램을 key, 원래 단어를 value로 하는 딕셔너리를 만든다.

3. 출력이 count값이 아니라, 원래 단어들이 묶인 리스트이기 때문에, 같은 key인 단어가 나올 때마다 value 리스트에 원소를 추가하는 식으로 만든다.

 

참고: 1. 과정을 실행하면서 알게 된 사실인데, attriute 인 .sort()의 경우 문자열에 적용할 수 없는 반면, 내장함수인 sorted()의 경우 문자열에도 잘 적용이 되었다.

 

a = 'dream'
a.sort()

AttributeError Traceback (most recent call last) <ipython-input-34-7365cacbbacb> in <module>

          1 a = 'dream'

----> 2 a.sort()

AttributeError: 'str' object has no attribute 'sort'

 

sorted(a)

out : ['a', 'd', 'e', 'm', 'r']

풀이

내가 제출한 코드는 아래와 같다.

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        result = {}
        for str in strs:
            s = ''.join(sorted(str))
            result[s] = result.get(s,[]) + [str]
        return result.values()

잘 통과되었으나 런타임이 92ms 가 나왔다. 앞에서 풀어봤던 다른 문제들 보다 더 나오는 셈.

그래서 책을 참고 했는데, 

1. 빈 딕셔너리를 collecionts 모듈의 .defaultdict() 를 활용하여 만들었다.

2. 딕셔너리에 원소를 추가할 때 .append()를 활용하였다.

 

라는 두 가지 점이 크게 달랐다.

 

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        result = collections.defaultdict(list)
        for str in strs:
            result[''.join(sorted(str))].append(str)
        return list(result.values())

이렇게 제출해도 런타임은 똑같이 92ms가 나왔다.

 

지난 번에 풀었던 <가장 흔한 단어>는  collections.Counter()를 활용하면 내가 짠 것 보다 훨씬 간편하게 해결이 되었는데, 이번 문제도  collections 라이브러리를 활용할 수 있었다.

내가 많이 활용해보지 않았던 라이브러리인데, 자주 활용할 수 있는 것들은 좀 더 익숙해질 필요가 있을 것 같다.