[LeetCode] 3. 그룹 애너그램

LeetCode 49번 문제는 정렬과 딕셔너리를 활용해서 쉽게 문제풀이가 가능하다.

 

입력으로 strs = ["eat","tea","tan","ate","nat","bat"]가 주어졌을때 아래와 같이 코딩을 하면 된다.

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

        result = collections.defaultdict(list)        
        for string in strs:

            result[''.join(sorted(string))].append(string)
        return list(result.values())

 

문제풀이의 핵심은 defaultdict(), sorted(), str.join() 이다.

For문을 돌면서 리스트에 있는 문자열을 하나씩 꺼내 string 변수로 받는다. 이제 string의 자료형은 'str'이 된다. sorted()함수를 통해 문자열을 정렬하면 아래와 같이 리스트를 반환한다.

 

a = 'eat'
sorted(a)
# ['a', 'e', 't']

 

따라서 이 문자열을 다시 묶어주는 작업을 진행해야한다. 구분자없이 리스트의 원소를 연결을 해야하기 때문에 ''.join(string)을 진행한다. 이러면 eat -> ['a', 'e', 't'] -> 'ate'로 변환된다.

이제 이것을 다시 딕셔너리에 Key, Value 형태로 묶어준다. 정렬이 완성된 값이 Key가 되며, 입력으로 받았던 string이 Value가 된다. 이 과정을 반복하면 'eat', 'ate', 'tea'는 모두 'aet'라는 Key를 가진 딕셔너리의 Value가 될것이다.

 

마지막으로 딕셔너리의 Values()를 활용하여 리턴해주기만 하면 된다.

만약 defaultdict() 를 사용하지 않고 일반 딕셔너리를 사용하면 문제가 발생한다.

우선 append()를 사용할 수 없다. 왜냐하면 만들어두었던 result변수에 Key가 없기때문에 Error가 발생한다. 이를 수정하기위해서 result[''.join(sorted(string))] = string 이런식으로 코딩을 하였다면, Key에 해당하는 Value가 덮어쓰기 되어 1개의 Value값만 존재하게된다.