[알고리즘, Python] 아나그램(Anagram) 묶기

오늘 풀어볼 문제는 Anagram끼리 묶는 문제다. 

 

여기서 Anagram이란 단어의 문자열은 같지만 순서는 다른 것들을 말한다.

 

예를 들면 "eat"과 "tea"는 모두 a, e, t 로 이루어진 단어지만 순서는 다르다.

 

Leetcode에서 문제보기

 

---

 

솔루션 1.

 

내가 처음 생각해낸 코드는 아래와 같았다.

 

우선 모든 단어를 돌며 정렬한 후 anagram이 존재하면 그 array에 넣어주고 없으면 result에 새로운 배열을 추가한다.

 

즉 ["eat", "tea", "hi", "hello", "ate"]가 있다고 했을 때

 

"eat"를 정렬하면 "aet"이다. anagrams에 존재하지 않는다. 추가해준다.

anagrams = ["aet"]

result = [["eat"]]

 

"tea"를 정렬하면 "aet"다. anagrams를 반복문으로 돌며 존재하는지 찾는다. 존재한다. enumerate를 사용해 index값과 anagram 값을 같이 발견했다.

 

anagrams와 각 anagrams를 묶은 배열, 즉 anagrams 와 result 가 같은 인덱스를 공유한다.

 

"aet"를 index 0 에서 찾았으니 그 집합도 result[0[에 있다는 소리다.

 

컨셉이 틀리진 않았다.

 

하지만 글로 읽기만 해도 굳이? 라는 생각이 들지 않는가?

 

실제로도 런타임이 무려 2776 ms로 하위 5% 결과였다. 왜일까?

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        
        anagrams = []
        result = []
        
        for s in strs:
            anagramExist = False
            sorted_s = ''.join(sorted(s))
            for index, anagram in enumerate(anagrams):
                if sorted_s == anagram:
                    result[index].append(s)
                    anagramExist = True
                    break
            if not anagramExist:
                anagrams.append(sorted_s)
                result.append([s])
        
        return result

반복문으로 서칭하는 것은 비효율적이다. 그냥 anagrams를 해시맵으로 구현하면 서치 속도가 O(1)이다.

 

즉 {"aet": ["tea", "ate", "eat"]} 로 구현하는게 낫다는 이야기다.

 

그러면 해시맵을 이용해서 다시 구현해보자.

 

 

솔루션 2.

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams = {}
        for word in strs:
            sortedWord = ''.join(sorted(word))
            if sortedWord in anagrams:
                anagrams[sortedWord].append(word)
            else:
                anagrams[sortedWord] = [word]
 
        return anagrams.values()

결과는 런타임 203 ms로 13배 가까이 빠른 속도를 보인다.

 

솔루션 1의 문제점은 anagrams의 삽입(insertion)과 찾기(lookup)였음을 알 수 있다.

 

참고로 Python의 x in s 의 시간 복잡도는 list에서 O(n)이다.

출처: TimeComplexity - Python Wiki

 

참고로 두 코드에서 메모리는 거의 차이 없었다.

---

Reference

1. https://leetcode.com/problems/group-anagrams/discuss/664252/Python-3-solution-detailed-explanation-faster-than-97.5