LeetCode 49(Groupd Anagrams, Python)

1. 문제 링크

• https://leetcode.com/problems/group-anagrams/

Group Anagrams - LeetCode

 

2. 문제 설명

• 문자열로 구성된 array strs가 주어졌을 때, anagrams로 그룹화하는 것
  • 여기서 anagram은 다른 단어나 구절의 글자들을 재배열하여 만든 단어나 구절을 가리키며, 보통 모든 원래의 글자를 정확히 한번 사용
• 예시1) strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 이면, 
  • aet 조합, atn 조합, abt 조합이 있으므로 
  • [["bat"], ["nat","tan"], ["ate","eat","tea"]]를 반환 (순서 무관 - return in any order) 

3. 기존 풀이 

• hash table을 사용하며, 
  • ''.join(sorted(i)) (문자열을 알파벳 순서로 정렬)가 hist_dict에 존재하는지를 확인
    
    • 만약 존재하지 않으면 새로 key를 만들어주고, 
    • 존재한다면 기존 리스트에 추가하는 구조로 코드를 짠다
• 최종적으로 hist_dict.values를 list 형태로 반환 

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        hist_dict = {}

        for i in strs:
            if ''.join(sorted(i)) not in hist_dict:
                hist_dict[''.join(sorted(i))] = [i]
            else:
                hist_dict[''.join(sorted(i))] += [i]
        
        return list(hist_dict.values())

• medium치고는 생각보다 간단했다. runtime 85%로 무난히 통과 

 

4. 다른 풀이

• 대부분 논리는 비슷하게 짠 것 같았다. ''.join(sorted(word))로 anagram이라면 같은 형태로 변형하는 과정을 거치고, hash table을 통해 append 시키는 구조 
• 항상 그냥 {}로 빈 껍데기를 만들어서 짰었는데, python 내장 라이브러리인 collections의 defaultdict 함수를 사용하는 경우가 많이 보였음 
• defaultdict(list)를 하면 기본값이 빈 리스트로 초기화가 되어있으며, 
  • 따라서 해당 key가 dictionary에 존재하는지에 대한 여부를 체크하지 않고 바로 append가 가능해서, 좀 더 간결하게 코드가 작성된다.
• 마찬가지로 defaultdict(int)를 하면 기본값이 0으로 초기화되고, defaultdict(str)를 하면 기본값이 ''로 초기화가 됨
  • 기존 방식인 {}과 런타임이나 메모리사용은 미미하거나 무시할 수준으로 차이가 없다고 함.
    • if ~ in dict: 이게 O(1)의 시간복잡도를 가진다고 함
  • 다만, 초기값 설정을 자동으로 헤주기 때문에, 코드가 좀 더 간결해지고 읽기 쉬워지는 장점이 존재 

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

 

5. 배운점

• defaultdict