[문자열 조작] 05 그룹 애너그램(Group Anagrams)

<LeetCode 문제>

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

Group Anagrams - LeetCode

문자열 배열을 받아 애너그램 단위로 그룹핑하는 문제입니다.

애너그램이란 어떤 문자열의 문자를 재배열하여 다른 문자열과 같아지는 것입니다.

<풀이>

문자열의 구성 알파벳을 기준으로 그룹핑이 필요하므로, 구성 알파벳을 뽑아야 합니다.

 

처음 문제를 풀 때, set()을 통해 구성 알파벳을 구하고 이를 key값으로 이용하려 했지만 문제가 있었습니다.

1. set은 mutable 자료형이므로 dictionary의 key가 될 수 없다.

2. 같은 알파벳이 여러 개 있는 문자열의 경우 set을 쓰면 특정 알파벳이 제거된다.

 

이러한 이유에서 set이 아닌 tuple을 이용했으며, tuple은 순서가 유의미하므로, 정렬을 하여 tuple 내의 순서는 의미가 없도록 하였습니다.

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        new_dict=defaultdict(list) #기본 value가 []
        for str in strs:
          key = tuple(sorted(str)) # 내부 알파벳 정렬해서 key값으로
          new_dict[key].append(str)
        return list(new_dict.values())

 

튜플이 아닌 join으로 리스트의 문자들을 묶어줄 수도 있습니다.

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        new_dict=defaultdict(list) #기본 value가 []
        for str in strs:
          new_dict[''.join(sorted(str))].append(str)
        return list(new_dict.values())

 

풀이에서 사용된 defaultdict에 list를 전달하면 기본 value가 []이 되어서 dictionary에 해당 key가 존재하는지 check할 필요 없이 바로 append할 수 있습니다.

 

<학습내용>

1. dictionary의 key는 immutable 자료형만 가능하다.(string, int, tuple) cf. mutable: (list, dictionary)
2. immutable 객체는 call by reference, mutable 객체는 call by value로 동작한다.
3. sorted()에 문자열을 전달하면 결과를 리스트로 전달해서 join()으로 합쳐야 한다.
4. 리스트 자료형에 제공되는 sort()는 제자리 정렬로 입력을 출력이 덮어 씌우고, sorted()는 정렬 결과를 별도로 리턴한다.
5. sort()와 sorted() 모두 key 옵션을 통해 정렬을 위한 함수를 지정할 수 있다. 일반 함수 또는 lambda함수를 이용할 수 있다.
6. 파이썬의 기본정렬은 팀소트(Timsort)를 이용한다.

<학습이 필요한 내용>

1. 정렬 종류별로 시간복잡도 + 각 특징 정리

 

https://github.com/HoYoungChun/Algorithm_PS/blob/master/String/LC_49.py

GitHub - HoYoungChun/Algorithm_PS: Baekjoon Online Judge, Programmers, LeetCode problem solving by Python, C++