분명히 애너그램 문제는 이전에도 풀어본 적이 있는데도 돌아가는 방법을 사용하는 버릇은 여전히 못 고치는 것 같다. 같은 알파벳의 조합으로 이루어져 있는 단어들을 애너그램이라고 한다.
eat, ate, tea 들이애너그램이다.
첫번 째로 시도한 풀이이다.
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
def alphabet_count(words):
alphabets = {}
for i in ascii_lowercase:
alphabets[i] = 0
for letter in words:
for key,val in alphabets.items():
if key == letter:
alphabets[key]+=1
return alphabets일일히 각 단어들을 알파벳 딕셔너리 안에 알파벳별로 정리해보았다.
결과:
input : ["eat","tea","tan","ate","nat","bat"]
{'a': 1, 'b': 0, 'c': 0, 'd': 0, 'e': 1, 'f': 0, 'g': 0, 'h': 0, 'i': 0, 'j': 0, 'k': 0, 'l': 0, 'm': 0, 'n': 0, 'o': 0, 'p': 0, 'q': 0, 'r': 0, 's': 0, 't': 1, 'u': 0, 'v': 0, 'w': 0, 'x': 0, 'y': 0, 'z': 0}
{'a': 1, 'b': 0, 'c': 0, 'd': 0, 'e': 1, 'f': 0, 'g': 0, 'h': 0, 'i': 0, 'j': 0, 'k': 0, 'l': 0, 'm': 0, 'n': 0, 'o': 0, 'p': 0, 'q': 0, 'r': 0, 's': 0, 't': 1, 'u': 0, 'v': 0, 'w': 0, 'x': 0, 'y': 0, 'z': 0}
{'a': 1, 'b': 0, 'c': 0, 'd': 0, 'e': 0, 'f': 0, 'g': 0, 'h': 0, 'i': 0, 'j': 0, 'k': 0, 'l': 0, 'm': 0, 'n': 1, 'o': 0, 'p': 0, 'q': 0, 'r': 0, 's': 0, 't': 1, 'u': 0, 'v': 0, 'w': 0, 'x': 0, 'y': 0, 'z': 0}
{'a': 1, 'b': 0, 'c': 0, 'd': 0, 'e': 1, 'f': 0, 'g': 0, 'h': 0, 'i': 0, 'j': 0, 'k': 0, 'l': 0, 'm': 0, 'n': 0, 'o': 0, 'p': 0, 'q': 0, 'r': 0, 's': 0, 't': 1, 'u': 0, 'v': 0, 'w': 0, 'x': 0, 'y': 0, 'z': 0}
{'a': 1, 'b': 0, 'c': 0, 'd': 0, 'e': 0, 'f': 0, 'g': 0, 'h': 0, 'i': 0, 'j': 0, 'k': 0, 'l': 0, 'm': 0, 'n': 1, 'o': 0, 'p': 0, 'q': 0, 'r': 0, 's': 0, 't': 1, 'u': 0, 'v': 0, 'w': 0, 'x': 0, 'y': 0, 'z': 0}
{'a': 1, 'b': 1, 'c': 0, 'd': 0, 'e': 0, 'f': 0, 'g': 0, 'h': 0, 'i': 0, 'j': 0, 'k': 0, 'l': 0, 'm': 0, 'n': 0, 'o': 0, 'p': 0, 'q': 0, 'r': 0, 's': 0, 't': 1, 'u': 0, 'v': 0, 'w': 0, 'x': 0, 'y': 0, 'z': 0}
alphabet_count 함수마다 딕셔너리를 만들기는 했는데, 단어별로 이 딕셔너리들을 비교하면서 같은 리스트 단위로 묶는 것에서 풀이가 막혔다.
우선 비효율적인 방법을 버리고
알파벳 순으로 단어를 배열하여 단어별로 비교가 수월하게끔 해보았다.
파이썬 알고리즘 인터뷰 저서의 풀이에서는 collection 모듈의 defaultdict를 사용한다.
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
anagrams = collections.defaultdict(list)
for words in strs:
anagrams[''.join(sorted(words))].append(words)
return list(anagrams.values())defaultdict(T)
deafultdict는 일반적인 딕셔너리와 달리 없는 키 값에 value를 넣더라도 그 없는 키 값에 해당하는 키를 생성해주어 오류를 방지하면서 동적으로 딕셔너리를 만들기 편하다는 장점이 있다.
먼저 리스트를 value로 가지는 애너그램 딕셔너리를 만들어주고, strs의 단어마다 sorted함수로 소팅을 해준다.
sorted("cba")와 같이 쓰면 abc로 값이 나오는 것이 아니라, ['a','b','c']처럼 리스트로 반환하기 때문에 abc처럼 만들어주려면 ''.join(sorted(words))와 같이 처리해줘야 한다. 따라서 딕셔너리의 키가 정렬된 알파벳 배열에 해당하는 단어들이 append 되어, 그 value들만 출력해주어서 원하는 답을 얻을 수 있다.
defaultdict의 인자 안에는 키에 해당하는 아이템의 형이 들어간다
defaultdict(int)면 {a:1, b:1, c:3} 대략 이런식
Counter
from collections import Counter
print(Counter('aaabbbcccccCCCDD'))Counter({'c': 5, 'a': 3, 'b': 3, 'C': 3, 'D': 2})
각 string의 요소들의 빈도수를 자동으로 세어 출력해준다.
