[파이썬 알고리즘 인터뷰] 4. 그룹 애너그램

https://github.com/onlybooks/algorithm-interview

GitHub - onlybooks/algorithm-interview: <파이썬 알고리즘 인터뷰> 95가지 알고리즘 문제 풀이로 완성하는

1. 문제: leetcode 49. Group Anagrams

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

 

2. 풀이

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

    #dict 만들기
    for letter in strs:
        sorted_strs[''.join(sorted(letter))].append(letter)

    return sorted_strs.values()

 

3. 배운 점

1) defaultdict

 python의 dict에서 존재하지 않는 키로 접근하면 보통 key error를 일으킨다. 그래서 조건문을 사용해서 key error를 피해줘야한다다. 하지만 defalut dict를 사용하면 존재하지 않는 키로 접근하면 처음에 설정한 기본값이 값으로 지정된다.

>>> int_dict = defalutdict(int)
>>> int_dict['key1']
0
>>> list_dict = defalutdict(list)
>>> list_dict['key2']
0

오늘의 문제처럼 키마다 여러 값을 추가해야 할 때, 키의 개수를 세어야 할 때 유용하게 사용할 수 있을 것 같다.

 

2) 정렬

list의 경우는 sort 메소드가 있다. 이는 in-place 정렬로써 추가적인 공간을 필요로 하지 않고, 출력값이 없다.

sorted() 함수를 사용해서 리스트, 문자열을 정렬할 수 있다. 이 함수는 다음과 같이 key로 하나의 인자를 가지는 함수를 지정해서 다양한 방법으로 정렬할 수 있다. 또한 list의 sort 메소드와 달리 정렬 결과를 리턴해준다.

>>> c = ['ccc', 'aa', 'd']
>>> sorted(c, key = len)
['d', 'aa', 'ccc']

>>> a = ['cde', 'cfc', 'abc']
>>> def fn(s): return s[0], s[-1]
>>> sorted(a, key = fn)
['abc', 'cfc', 'cde']

3) 새로운 배열을 만들기보다 기존의 자료구조를 활용해서 문제 풀기

 dict를 활용해서 문제 푸는 것을 처음 생각했을 때는 키, 값을 각각 원래 문자열, 정렬한 문자열로 가지는 dict를 만들고, 정렬한 문자열이 같은 것끼리 모아서 return을 위한 배열을 만들 계획을 했다. 하지만 정렬한 문자열을 키로, 원래 문자열을 값으로 받으면 따로 새로운 자료구조를 만들 필요 없이 dict를 한번만 만드는 걸로 끝날 수 있었다. 문제를 풀 때 효율적인 자료구조를 고민하면서 풀면 좋을 것 같다.