알고리즘/파이썬

[파이썬 알고리즘] 그룹 애너그램

귤먹는코더 2022. 5. 14. 01:24
728x90

입력 :

["eat", "tea", "tan", "ate", "nat", "bat"]

출력 :

[

    ["ate", "eat", "tea"],

    ["nat", "tan"],

    ["bat"]

]

 

풀이 1) 정렬하여 딕셔너리에 추가!

1. 정렬하여 비교하는 방법이 가장 간단 ! , 애너그램 관계인 단어들을 정렬하면, 서로 같은 값을 갖게 되기 때문

2. sorted()는 문자열도 잘 정렬하고 결과를 리스트 형태로 리턴

3. 같은 애너그램을 가진 원소들끼리 묶어야 하므로, 애너그램을 key, 원래 단어를 value로 하는 딕셔너리를 만든다.

4. 출력이 count 값이 아니라, 원래 단어들이 묶인 리스트이기 때문에, 같은 key인 단어가 나올 때마다 value 리스트에 원소를 추가하는 식으로 만든다.

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        result = {}
        for str in strs:
            s = ''.join(sorted(str))
            result[s] = result.get(s,[]) + [str]
        return result.values()

출처: https://rollingsnowball.tistory.com/117 

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

 

이분 께서 잘 설명하셨는데 이해가 될듯 말듯 이번 주말까지는 다 정복하자 어떻게서든 !

728x90