Group Anagrams [leet code 49]

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

 

 

애너그램 문제이며,

애너그램이란 문자열이 주어졌을 때, 알파벳의 나열 순서를 다르지만 그 구성이 일치하면 두 단어는 아나그램이라고 합니다.

ex)  a = "atta"    b = "taat" 일때 나열 순서는 다르지만 a 2개 t 2개로 a 와 b는 Anagram이라고 표현한다. 

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Example 2:

Input: strs = [""]
Output: [[""]]
Example 3:

Input: strs = ["a"]
Output: [["a"]]

 

문제는 strs 리스트 형태로 각 원소들이 str 형태가 주어지면 anagram 문자끼리 list로 묶어서 return하는 문제다.

다양하게 문제 풀이를 진행할 수 있으며, 여기서는 list 비교와 dict 형태로 두가지 풀이를 해볼 예정이다.

 

 

 

list방식으로 문자열을 비교하면 다음과 같이 풀이할 수있을 것이다.

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # 결과를 저장할 리스트
        result = []
        # 이미 그룹화된 문자열들을 추적할 리스트
        seen = [False] * len(strs)
        
        for i in range(len(strs)):
            if seen[i]:
                continue
            # 현재 문자열을 포함할 새로운 그룹 생성
            group = [strs[i]]
            seen[i] = True
            # 나머지 문자열들과 비교
            for j in range(i + 1, len(strs)):
                if not seen[j] and sorted(strs[i]) == sorted(strs[j]):
                    group.append(strs[j])
                    seen[j] = True
            # 그룹을 결과 리스트에 추가
            result.append(group)
        
        return result

 

위 코드로 Run을 해보면 Testcase는 잘 통과하는 것을 볼 수 있겠지만, Submit를 하게되면 Time Limit Exceeded가 뜨는 것을 볼 수 있을 것이다.

 

왜? 

Constraints:

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters.

제약조건을 보면 str 길이가 길어지면 비교도 많아지고 이중포문을 돌며 리스트에 저장되면서 각 문자열을 다른 모든 문자열과 비교하기 때문인데, 다음과 같이 코드를 수정하면 느리지만 통과할 수 있다.

 

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # 결과를 저장할 리스트
        result = []
        # 정렬된 문자열 리스트
        sorted_strs = []
        
        for s in strs:
            # 문자열을 정렬한 후 그 결과를 저장
            sorted_s = ''.join(sorted(s))
            
            # 정렬된 문자열이 이미 존재하는지 확인
            found = False
            for i in range(len(sorted_strs)):
                if sorted_strs[i] == sorted_s:
                    result[i].append(s)
                    found = True
                    break
            
            # 만약 새로운 아나그램 그룹이라면 새로 추가
            if not found:
                sorted_strs.append(sorted_s)
                result.append([s])
        
        return result

 

모든 문자열을 비교하던 것에 비해 효율적으로 비교하여시간 복잡도가 크게 줄어드는데, 사실 제일 간편하게 dict를 사용하면 삽입 삭제 등 비교하는게 시간 효율이 좋아질 것이다.

 

최종 코드는 다음과 같습니다.

 

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # 아나그램 그룹을 저장할 딕셔너리 생성
        results = {}
        
        # 주어진 문자열 배열에서 각 문자열을 순회
        for s in strs:
            # 문자열을 정렬한 후 그 정렬된 문자열을 키로 사용
            sorted_str = ''.join(sorted(s))
            
            # 정렬된 문자열이 딕셔너리에 없다면 새 리스트 생성
            if sorted_str not in results:
                results[sorted_str] = []
            
            # 해당 리스트에 원래 문자열 추가
            results[sorted_str].append(s)
        
        # 아나그램 그룹들을 리스트로 반환
        return list(results.values())