코딩에 대한 이해력을 높이기 위한 작성된 글입니다.
여기의 내용은 @NeetCode 유튜버 동영상을 기반으로 작성되었으므로, 문제 발생 시 즉각적으로 삭제하도록 하겠습니다.
문제
풀이
Anagram은 영어의 말장난으로서, 단어의 문자를 재배열하며 다른 뜻을 가지는 다른 단어로 바꾸는 것을 뜻하게 됩니다.
- Sorting
예를 들어 보겠습니다. "nat"와 "tan"이라는 string의 anagram은 정렬을 통해 "ant" 이라는 같은 결과물을 도출 해낼 것 입니다. 그렇다면, 모든 List의 String을 정렬을 통해 비교하게 된다면 Time Complexity O(nlogn * 배열의 길이) 차원에서 비효율적 일 것 입니다.
- HashMap
각 String의 element 즉 알파벳 개수를 파악하게 된다면, character 개수는 똑같을 것 입니다. 예를 들어 보겠습니다. "nat"와 "tan"의 알파벳 charater 수는 똑같을 것 입니다. Hashmap를 통하여 key:value 형태로 저장하게 된다면, anagram에 대해 파악 할 수 있을 것 입니다.
여기서 key는 "알파벳 개수" 될 것 이고, value는 list 각각의 string이 될 것 입니다. 이에 Time Complexity은 O(배열의 길이 * N) 이 될 것 입니다.
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
ans = collections.defaultdict(list)
for s in strs:
count = [0] * 26
for c in s:
count[ord(c) - ord("a")] += 1
ans[tuple(count)].append(s)
return ans.values()
- defaultdict 사용한 이유 : Hash Map 충돌 방지.
- count[ord(0) - ord(a)] : 예를 들어, a의 ascii가 30이라고 가정 하였다면, ord(0) - ard(a) 는 0을 반환하고, ord(1)-ord(a)는 1를 반환 할 것 입니다. 이를 통하여 Index의 값을 알파벳 값과 똑같게 0부터 25까지 지정할 수 있습니다.
- String 값을 반환하기에 result.values()
