[알고리즘 문제 풀이] 그룹 애너그램

문제

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

---

예제1

입력

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

출력

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

---

이 문제를 해결하는 방법은 먼저 입력으로 들어온 값을 정렬해보고, 각 정렬한 값의 딕셔너리키의 값에 입력값을 추가하는 것이다.

말로 표현하는 것이 어려우니 아래 그림을 보면 쉽게 이해할 수 있다.

1. 먼저 입력으로 들어온 strs 리스트 내부의 원소를 하나씩 word로 옮기고,
2. word에 들어온 원소를 정렬한 후 다시 문자열로 합치고 딕셔너리의 값에 추가한다.
3. 키와 값이 추가된 딕셔너리가 완성되었다면, 각 값들을 출력한다.

코드로 위 과정을 진행하면 이 문제를 풀 수 있게 된다. 하지만 만약 존재하지 않는 키를 삽입하려 하면 KeyError가 발생하므로, 에러가 나지 않도록 항상 디폴트를 생성해주는 defaultdict( ) 함수를 이용하여 딕셔너리를 선언해주어야 가능하다. defaultdict 함수는 collections 모듈을 포함해야 사용할 수 있다. 이렇게 진행하면 매번 키 존재 여부를 체크하지 않고 비교 구문을 생략해서 구성할 수 있다.

 

전체 코드는 다음과 같다.

# input: ["eat", "tea", "tan", "ate", "nat", "bat"]
# output:
# [
#            ["ate","eat","tea"],
#            ["nat","tan"],
#            ["bat"]
# ]

import collections
def groupAnagrams(strs: list[str]) -> list[list[str]]:
    anagrams = collections.defaultdict(list)

    for word in strs:
        anagrams[''.join(sorted(word))].append(word)
    return list(list(anagrams.values()))

strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(groupAnagrams(list(strs)))

---

알게된 점

문자 재배열 시 알파벳 순으로 정렬 후 join( ) 함수를 통해 같은 문자로 구성된 문자열을 정리할 수 있다.

정렬한 값을 키로 하여 딕셔너리에 추가하는 방법

 

공부할 것

다양한 정렬 방법

팀소트