[리트코드] Group Anagrams(python)

리트코드, Group Anagrams_그룹 애너그램

 

TL;DR

• 문제에서 주어진 조건을 구현할 수 있는지
• python의 자료형인 dictionary를 활용할 수 있는지

문제 분석

1. 주어진 문자열에 대해서 같은 애너그램을 가진 문자열끼리 묶어야 한다.
2. 순서에 상관없이 정답을 반환하면 된다.
3. 애너그램은 문자열을 이루고 있는 문자를 재배치하여 만들 수 있는 서로 다른 문자열을 의미한다.

 

- 1 ~ 2 : 해결해야 하는 문제와 출력에 대한 조건을 설명하고 있다.

- 3 : 애너그램에 대한 내용을 설명하고 있다. 자세한 내용은 입출력 형태에서 살펴본다.

입출력 형태

입출력 예시

 

- strs : 여러 개의 문자가 들어 있는 리스트가 주어진다.

- output : 애너그램끼리 묶은 리스트를 반환한다.

  - strs에서 'eat', 'tea', 'ate'는 'a, e, t'로 이루어진 애너그램이다.

  - 'tan', 'nat'은 'a, n, t'로 이루어진 애너그램이다.

  - 'bat'는 'a, b, t'로 이루어진 애너그램이다.

  - 같은 애너그램끼리 묶어서 결과물을 반환해야 한다.

풀이

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
    	# defaultdict : 존재하지 않는 key로 인한 에러를 방지하기 위해서 사용
        # 존재하지 않는 key에 value 추가 시, 에러 없이 삽입해준다.
        dicts = collections.defaultdict(list)
        
        for _str in strs:
        	# 주어진 문자를 알파벳순으로 정렬하여 같은 애너그램을 key로 dict에 저장한다.
            dicts[str(sorted(_str))].append(_str)
            
        return list(dicts.values())

 

- `collections.defaultdict(list)`

  - defaultdict를 쓰는 이유는 일반적인 dict는 존재하지 않는 key를 삽입할 경우 에러가 발생하기 때문이다.

- `dict[str(sorted(_str))].append(_str)

  - `sorted(_str)` : 주어진 문자열 strs에 들어있는 각 문자열을 정렬한다.

  - 예시에서 'eat'는 'aet'를 key, 'eat'가 value인 채로 dict에 삽입된다.

  - 이 구문이 실행된 이후 dict의 모습은 다음과 같다.

{
    "aet" : ["eat", "tea", "ate"],
    "ant" : ["nat", "tan"],
    "abt" : ["bat"]
}

 

- 애너그램 별로 그룹을 지었기 때문에 values()를 통해 key를 제외한 value들만 가져와서 리스트의 형태로 반환한다. 리스트이 형태인 이유는 문제에서 원하는 반환형이기 때문이다.

- 테스트 케이스에서와 순서가 다르게 출력될 수 있지만, 문제 조건에서 순서에 상관없이라고 명시되어 있기 때문에 별도의 처리를 하지 않아도 된다.