[알고리즘][문자열 조작] - 5. 그룹 애너그램

 

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님'을 보고 작성되었습니다.

---

😎문제 : https://leetcode.com/problems/group-anagrams/ 

Group Anagrams - LeetCode

문자열 배열을 받아 애너그램 단위로 그룹핑하라.

---

[애너그램이란?]

• 일종의 언어유희로 문자를 재배열하여 다른 뜻을 가진 단어로 바꾸는 것을 말한다. '어구전철' 이라고도 부르며 과거 유럽에서는 근대까지 이러한 언어유희가 매우 유행했다고 한다. 애너그램의 우리말 예로는, '문전박대'를 '대박전문'으로 바꿔 부르는 단어 등을 들 수 있다.
• 애너그램을 판단하는 가장 간단한 방법은 정렬해서 비교하는 것이다. 애너그램 관계인 단어들을 정렬할 때 서로 같은 값을 갖게 되기 때문이다

 

 

 

[정렬하여 딕셔너리에 추가]

애너그램을 판단하는 가장 간단한 방법은 정렬하여 비교하는 것이다. 왜냐하면 애너그램 관계인 단어들은 정렬하면, 서로 같은 값을 갖게 되기 때문이다. sorted( )는 문자열도 잘 정렬하며 결과를 리스트형태로 리스형태로 리턴하는데 이를 다시 사용하기 위해 join( )으로 합쳐 이 값을 키로 하는 딕셔너리로 구성한다. 

import collections


class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrames = collections.defaultdict(list)

        for word in strs:
            anagrames[''.join(sorted(word))].append(word)

        return list(anagrames.values())

 

 

 

• anagrames = collections.defaultdict(list)
• 가상의 딕셔너리로 만들어주는데 이때 디폴트 값이 list인 경우를 말한다.
• 매번 키 존재 여부를 체크하지 않고 비교 구문을 생략해 간결하게 구성한다.

 

• anagrames[''.join(sorted(word))].append(word)
• 정렬한 값을 키로해 딕셔너리에 추가해준다. 
• 만약 존재하지 않는 키를 삽입할 경우 keyError가 발생한다. 그래서 이를 방지하기 위해 항상 디폴트를 생성해주는 defaultdict( )로 선언해준다. 

 

• return list(anagrames.values())
• list형태로 출력하기에 list로 돌려주고 애너그램인 값들만 돌려준다.

 

 

 

[실행 속도 비교]