[2024] day 37. 49. Group Anagrams

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 2월 6일 (화)
Leetcode daily problem

49. Group Anagrams

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

Problem

문자열 배열 strs가 주어질 때, 배열의 문자열의 철자 바꾸기를 통해서 배열의 다른 원소와 같은 철자가 될 수 있는 anagram 끼리 그룹화하여 리스트로 반환한다.

Solution

array

문자열 관련 알고리즘은 알파벳 기준이라면 알파벳 수 a-z인 26개의 배열을 만들어놓고 해쉬를 이용해서 찾아내는 방법이 자주 나온다.
이번 anagram 찾는 것도 주어진 배열에서 문자열의 하나씩 탐색하면서 26개(a-z) 사이즈의 배열에 해당하는 빈도를 체크한다.
문자 배열의 원소당 26개의 사이즈 배열에 체킹한 것을 tuple로 만들어 key로 해서 하나의 해쉬를 또 생성한다.
두번째 해쉬맵은 문자열 26 사이즈에 해당하는 해쉬맵이다.
두 번째 해쉬맵의 26사이즈의 tuple을 키로 하고 해당하는 문자열을 value 로해서 마지막에 해당 values들을 반환하면, 해당 문자열끼리 리스트로 담아진 2-D 리스트가 반환된다.

Code

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        ans = defaultdict(list)
        for s in strs:
            tmp = [0] * 26
            for c in s:
                tmp[ord(c)-ord('a')] +=1
            ans[tuple(tmp)].append(s)

        return ans.values()

Complexicity

시간 복잡도

문자열 리스트를 순회하여 각 문자열의 길이를 확인하는 데 O(n)의 시간이 소요되고, 각 문자열을 탐색하여 각 문자의 빈도를 카운트하므로 문자열의 길이에 따라 O(k)의 시간이 소요된다.
총 시간 복잡도는 O(n * k)이다.

공간 복잡도

그룹화된 아나그램을 저장하기 위해 튜플로 변환하므로 문자열 리스트의 총 문자 수인 O(n) 이다.

---