[LeetCode] #49. Group Anagrams (python)

문제

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

Group Anagrams - LeetCode

 

애너그램 : 문자를 재배치해서 단어나 문구가 나오게 하는 것

같은 문자로 구성된 단어들끼리 묶어서 반환하면 된다.

 

예시 입출력

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

 

풀이

내 풀이

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

        cnt_list=[]
        output=[]

        for s in strs:
            cnt=collections.Counter(s)

            if sorted(cnt.elements()) not in cnt_list:
                cnt_list.append(sorted(cnt.elements()))
                output.append(list(s))
            else:
                idx=cnt_list.index(sorted(cnt.elements()))
                output[idx].append(s)

        return output

이전 문제에서 알게된 Counter를 사용해서 문제를 풀어봤다.

• 해당 단어가 어떤 문자로 구성되어 있는지를 Counter를 사용해 확인한다.
• elements 함수를 사용해 어떤 문자로 구성되어있는지 확인한다.
• 해당 문자로 구성된 것이 이미 존재하면 같은 리스트에 추가한다.
  

 

책 풀이

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

        words=collections.defaultdict(list)

        for s in strs:
            words[''.join(sorted(s))].append(s)

        return list(words.values())

애너그램을 판단하는 가장 간단한 방법 : 정렬

• 처음에 기본 딕셔너리를 리스트 형태로 생성한다.
• 정렬한 단어를 키 값으로 사용하고 value 값으로는 원래 단어를 추가한다.
• 딕셔너리의 value 값들을 리스트 형태로 반환한다.

 

참고한 책 : 파이썬 알고리즘 인터뷰