Group Anagrams :
https://neetcode.io/problems/anagram-groups/question
문제 파악
- 문자열들이 담긴 배열(
strs)이 주어질 때, 배열 안의 anagram에 해당하는 문자열끼리 묶어서 반환하기
문제 핵심
- 문자열을 직접 비교하지 않고 anagram 여부를 대표하는 공통된 키(key)를 만들어서, 같은 키를 가지는 문자열들을 하나의 그룹으로 묶음
사고흐름
- 여기서 필요한 핵심 ADT는 anagram을 대표하는 값과 그 문자열을 담을 수 있는 Map/Dictionary , 그리고 각 anagram을 저장하는 배열
- 여기서 각 문자열의 빈도를 정렬 기반으로 찾으면 정렬 비용이 발생하므로, 문자 빈도 기반으로 풀기 위해서 배열로 빈도수를 체크함
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
seen = {}
for s in strs:
alpha = [0] * 26
for c in s:
alpha[ord(c)-ord('a')] +=1
target = tuple(alpha)
if target not in seen:
seen[target] = [s]
else:
seen[target].append(s)
return [s for _, s in seen.items()]시간복잡도 O(nk), 공간복잡도 O(n26)
개선
pythonic 하게 만들기
if key not in seen:
seen[key] = [s]
else:
seen[key].append(s)대신에 defaultdict() 사용
from collection import defaultdict
seen = defaultdict(list)
seen[key].append(s)로 코드 간결성 높히기
마지막 return 하는 부분도
return [s for _,s in seen.items()] 보다는
return list(seen.values())즉, pythonic 한 개선한 풀이
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
from collections import defaultdict
seen = defaultdict(list)
for s in strs:
alpha = [0] * 26
for c in s:
alpha[ord(c)-ord('a')]+=1
target = tuple(alpha)
seen[target].append(s)
return list(seen.values())
추가
[1] tuple은 왜 Hashable 인가?
처음에 alpha의 배열을 seen에 넣으려고 할 때 해당 배열은 immutable 하지 않아서 (hashable 조건에 맞지 않아서) tuple로 바꾸는 과정을 추가했다.
Hash Table(Dictionary)의 key는 반드시 hashable 해야한다.
Hashable ?
어떤 객체가 hashable 하다는 것은
(1) hash(x)를 호출할 수 있고
(2) 객체의 값이 변하지 않으며 (immutable)
(3) 같은 값 -> 같은 hash 값
이 보장되어야 한다.
위의 배열 tuple로 바꾸기전의 alpha의 list는 내부 값이 바뀔 수 있고, hash table에 넣은 뒤 값이 바뀌면 위치가 깨져서 해시 무결성이 붕괴된다. 그래서 생성 이후 값이 변경 불가능한 tuple로 바꿔서 key로 넣었다.
tuple의 hash는 내부 원소들의 hash를 조합해서 만들기 때문에 tuple 안의 모든 원소도 hashable 해야 한다.
예)
hash((1, "a", (2,3))) # OK
hash((1, [2,3])) # X -> list 원소는 hashable 아님[2] 정렬 방식과 빈도 방식의 트레이드 오프
정렬 방식은 구현이 간단하지만 문자열마다 O(k log k)의 비용이 든다.
반면 빈도 방식은 알파벳이 제한된 경우 O(k)로 key를 만들 수 있어서 전체 시간복잡도를 줄일 수 있다. 따라서 입력 크기가 크거나 성능이 중요한 경우 빈도 방식을 사용하는 것이 좋다.
