[LeetCode 49번] Group Anagrams - (python)

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

Group Anagrams - LeetCode

 

 

해석

strs 라는 문자열이 들어있는 배열이 주어졌을때, 같은 anagram 끼리 묶는다. 

**anagram은 문자를 재배열해서 다른 뜻을 가진 단어로 바꾸는 것을 말한다.**

 

Idea

배열에 담긴 단어들을 같은 문자로 이루어진것 끼리 묶어야 한다. 각 단어들이 동일한 anagram인지를 판단할 수 있어야 한다.

그러기 위해서 각 단어에서 단어를 구성하고 있는 문자를 오름차순으로 정렬한 단어를 새로 만들고 그걸 기준으로 비교한다.

단어를 오름차순으로 정렬한다면 같은 anagram끼리는 같은 값을 가지게 된다.

이때 딕셔너리(해쉬)를 이용하면 쉽게 연산을 저장할수 있는데, 같은 애너그램끼리는 같은 키를 갖게 할 수 있다.

 

 

 

python

파이썬의 경우 d.values() 라는 함수를 사용하면 딕셔너리에 있는 value 값들만 가져올 수 있고 return 형태에 따라 list에 담아주었다.

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        d = dict()

        for s in strs:
            sorted_string = ''.join(sorted(s))

            if sorted_string not in d:  # 정렬된 문자열이 딕셔너리에 없으면
                d[sorted_string] = [] # 해상 문자열을 키값으로 갖는 (key,value) 추가
                # 이때 값(value)으로는 빈 배열을 추가하는데 이는 동일한 애너그램을 가진 문자열을 모두 배열에 넣어서
        		# return 해야 되기 때문이다.
            
            d[sorted_string].append(s) # value 추가

        return list(d.values())