[LeetCode_49] 그룹 애너그램

파이썬으로 배우는 알고리즘 책을 공부하며 풀었던 LeetCode문제들을 재정리해보자.

 

# 문제 설명 

49번 Group Anagrams은 문자열 배열을 받아 애너그램 단위로 그룹핑하는 문제이다.

 

* 애너그램 : 문자를 재배열하여 다른 뜻을 가진 단어로 바꾸는 것 

Example

 

 

# 풀이방법 1 - 정렬 후 딕셔너리에 저장

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
     
        output = []
        anagrams = {} # dictionay for check anagram's Index in 'output' list
        insertIdx = 0
        
        for _str in strs :   
            sortedStr = "".join(sorted(_str))
            
            if sortedStr in anagrams : 
                output[anagrams[sortedStr]].append(_str)
            else :
                anagrams[sortedStr] = insertIdx
                output.insert(insertIdx, [_str])
                insertIdx += 1
         
                
        return output

 

- anagrams 딕셔너리 : output 리스트를 관리하기 위한 딕셔너리로, 키는 애너그램 문자열을, 값은 해당 애너그램이 리스트의 몇 번째 인덱스에 있는 지 수정할 것  

- insertIdx 변수 : output 리스트에 넣을 때 마지막 인덱스를 알기 위해 둔 변수 

- output 리스트 : 애너그램을 저장하는 리스트  

1. 리스트의 한 단어를 정렬한 후 ouput 리스트에 넣기 위해 먼저 anagrams 딕셔너리를 확인하여, 이전에 해당 애너그램이 쓰였는지 확인한다.

2. 만약 없다면 딕셔너리에 해당 애너그램을 저장하는 리스트의 인덱스를 저장 후, 리스트에 애너그램을 저장한다.

있다면 딕셔너리에서 해당 애너그램이 저장된 리스트 인덱스를 찾아서 리스트에 저장한다. 

 

| 핵심 |

sortedStr = "".join(sorted(_str))

sorted만 사용하면 배열이라, 문자열로 바꾸기 위해서 "".join을 이용한다.

 

# 풀이 방법 2 - 정렬 후 딕셔너리에 저장 (책 풀이)

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

 

책의 방법은 리스트에 따로 저장 안 하고, 딕셔너리에 value을 뽑아 list로 바꾸면 됨 

 

| 핵심 |

anagrams = collections.defaultdict(list)

anagrams[''.join(sorted(word))].append(word)

 

 

 

# 결과