LeetCode #049 - Group Anagrams(그룹 애너그램) 문제 풀이

문제

문제의 애너그램은 특정 문자열의 문자를 재배치하여 만든 새로운 문자열이며, 문제에서는 여러 개의 문자열이 배열로 주어질 때 애너그램으로 짝짓고 반환할 것을 요구하였다. 문제를 보자마자 엑셀에서의 '중복 제거'가 떠올랐다. 즉, 특정 대상의 통계를 구하기 위해서는 해당 대상을 중복 제거하여야 한다. 이를 가능케 하는 방법으로 다음과 같이 크게 2가지를 떠올려보았다.

1. 문자열을 구성하는 문자의 ascii 코드의 총 합을 기준으로 중복 제거가 가능하다.
2. 문자열을 구성하는 문자를 정렬하면 중복을 제거할 수 있다.

이 중에서 두 번째 방법이 훨씬 직관적인 코드로 나타낼 수 있다고 생각하여 두 번째 방법으로 시도해보았다.

풀이

딕셔너리를 사용한 해시테이블 생성

딕셔너리의 key는 문자열의 문자를 정렬하여 만든 새로운 문자열로 하고, value는 빈 리스트로 한다.

groups = {''.join(sorted(word)): [] for word in strs}

해시테이블 데이터 입력

입력받은 문자열 리스트를 반복하는 동안 key 값을 현재 문자를 정렬한 새로운 문자열로 하여 딕셔너리에 접근하고, key에 해당하는 리스트에 현재 문자열을 추가한다.

for word in strs:
    groups[''.join(sorted(word))].append(word)

최종 결과 반환

딕셔너리에서 value만 리스트로 반환한다.

return list(groups.values())

전체 코드

from typing import List


class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        words = {''.join(sorted(word)): [] for word in strs}

        for word in strs:
            words[''.join(sorted(word))].append(word)

        return list(words.values())