[LeetCode] GroupAnagrams

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

Group Anagrams - LeetCode

문제설명 :

  문자열이 있을때 같은문자가 들어있는 경우 그룹(리스트)로 묶어 정답 리스트에 추가한다.

  같은문자열이 없는경우 하나의 문자열을 리스트에 추가해 정답 리스트에 추가한다.

compare_set = set()

for s in strs:
    new_s = ''.join(sorted(s))
    if new_s not in compare_set:
        compare_set.add(new_s)

ex) 다음과 같은 배열이 주어졌을때

strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

compare_set은 set 집합을 이용해 정렬된 unique한 문자열만 저장한다.

"eat", "ate", "tea" -> "aet" 

"tan", "nat" -> "ant"

"bat" -> "abt"

즉, compare_set = {'abt', 'ant', 'aet'} 으로 저장된다.

 

2. 집합과 strs 를 비교했을때 같은 문자열이 들어있는 경우 리스트를 만들어 추가한 뒤 정답 answer 리스트에 추가한다.

answer = []
for s in compare_set:
    li = list()
    for tmp in strs:
        word = ''.join(sorted(tmp))
        if word == s:
            li.append(tmp)
    answer.append(li)

3. 출력화면

[['bat'], ['tan', 'nat'], ['eat', 'tea', 'ate']]

 

 

<전체코드>

class Solution:
    def groupAnagrams(self, strs):
        compare_set = set()
        for s in strs:
            new_s = ''.join(sorted(s))
            if new_s not in compare_set:
                compare_set.add(new_s)
        print(compare_set)
        answer = []
        for s in compare_set:
            li = list()
            for tmp in strs:
                word = ''.join(sorted(tmp))
                if word == s:
                    li.append(tmp)
            answer.append(li)
        return answer

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

 

하지만 제출결과 ㅠ_ㅠ 항상 만나게 되는 시간초과..

Time Limit Exceeded!!

 

# 함수 실행시간을 측정해보자

파이썬 모듈 import time 을 추가한다

start = time.time()
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(Solution().groupAnagrams(strs))
end = time.time()
print(end-start)

 

결과:

3.0994415283203125e-05 초

 

개선

글을 찾아보니 dict() 을 사용한 방법이 있었다.

hash_map = {}
for s in strs:
    new_s = ''.join(sorted(s))
    if new_s in hash_map:
        hash_map[new_s].append(s)
    else:
        hash_map[new_s] = [s]

위에서 집합으로 만들어두었던 compare_set = {'abt', 'ant', 'aet'} 각각이 하나의 key가 되는 것

 

실행결과

{'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat'], 'abt': ['bat']}

 

실행시간

2.5033950805664062e-05

 

전체코드

import time
class Solution:
    def groupAnagrams(self, strs):
        hash_map = {}
            for s in strs:
                new_s = ''.join(sorted(s))
                if new_s in hash_map:
                    hash_map[new_s].append(s)
                else:
                    hash_map[new_s] = [s]
            print(hash_map)
            return list(hash_map.values())

start = time.time()
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(Solution().groupAnagrams(strs))
end = time.time()
print(end-start)