Group Anagrams | LeetCode 778 | Python3 🐍

 

📄 목차

 

🤔 문제 : Group Anagrams | LeetCode 778

문제: https://leetcode.com/explore/interview/card/top-interview-questions-medium/103/array-and-strings/778/
문자열의 리스트가 주어졌을때, 같은 문자 구성으로 순서만 바뀐 문자열을 묶어서 반환하는 문제입니다. 

예를들어 abc, acb, bac, bca, cab, cba가 하나의 그룹으로 묶입니다. 

 

💡 풀이

1. 접근 - '같은 문자들로 구성된 문자열'임을 어떻게 판단할까? 

이 문제의 핵심은 같은 문자들로 구성된 문자열임을 어떻게 판단할지입니다.

같은 문자들로 구성된 문자열은 같은 문자열로 바꿔서 판단하면 되겠죠. 

저는 문자열을 오름차순으로 정렬하는 방법을 사용했습니다.

 

2.  풀이

from typing import List
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        sorted_string_set = {}
        grouped_str_list = []
        targetIndex = 0
        for s in strs:
            sorted_str = str(sorted(s))
            if sorted_str in sorted_string_set:
                grouped_str_list[ sorted_string_set[ sorted_str ] ].append(s)
            else:
                sorted_string_set[ sorted_str ] = targetIndex
                targetIndex += 1
                grouped_str_list.append([s])

        return grouped_str_list

print(Solution().groupAnagrams(["eat","tea","tan","ate","nat","bat"]))

 

Time Complexity
문자열 정렬 : O(klogk), k는 문자열 길이
set에서 문자열 탐색 : O(1)
Space Complexity
정렬된 문자열만 set에 중복없이 저장합니다.
최악의 경우 O(n)이겠네요. (모든 문자열이 anagram이 아닌 경우)

 

3. 자료구조 및 함수 선택에 따른 성능의 차이 

처음에도 로직은 거의 동일했는데, 수행시간이 거의 9배나 크게 나왔습니다. 

 

다른점은 아래 두가지입니다. 

1. sorted_string_list -> set (906ms -> 173ms)

2.  ''.join(sorted(str)) -> str(sorted(s)) (173ms -> 112ms)

 

아래는 처음 제출한 코드와 성능입니다.

from typing import List

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        sorted_string_set = []
        grouped_str_list = []
        targetIndex = 0
        for str in strs:
            sorted_str = ''.join(sorted(str))
            group_id = sorted_string_set.index(sorted_str) if sorted_str in sorted_string_set else -1
            if group_id < 0 :
                group_id = targetIndex
                targetIndex += 1
                sorted_string_set.append(sorted_str)
                grouped_str_list.append([str])
            else:
                grouped_str_list[group_id].append(str)

            # print(sorted_string_set)
        # print(grouped_str_list)
        return grouped_str_list

 

 

python에서 set과 dictionary는 Hashmap 기반이기에 insert에 O(1)밖에 걸리지 않습니다.

반면 리스트에서의 time complexity는  O(n) 입니다.

 

참고) 파이썬 기본 자료구조의 time complexity 

https://wiki.python.org/moin/TimeComplexity

TimeComplexity - Python Wiki