[Leetcode] 49. Group Anagrams_해설, 풀이, 설명

---

안녕하세요, HELLO

 

오늘은 Leetcode 알고리즘 문제 '49. Group Anagrams'에 대해서 살펴보고자 합니다.

 

알고리즘 문제, 코드, 해설 그리고 Leetcode에서 제공해준 solution 순서대로 정리하였습니다.

---

STEP 1. 'Group Anagrams' 알고리즘 문제

 

STEP 2. 'Group Anagrams' 코드(code)

 

STEP 3. 'Group Anagrams' 해설

 

STEP 4. 'Group Anagrams' solution

 

반응형

 

STEP 1. 'Group Anagrams' 알고리즘 문제

 

Given an array of strings strs, group the anagrams together. You can return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

 

문자열 배열 strs가 주어지면 철자 바꾸기를 함께 그룹화합니다. 어떤 순서로든 답변을 반환할 수 있습니다. 애너그램 (Anagram)은 일반적으로 모든 원래 문자를 정확히 한 번 사용하여 다른 단어나 구문의 문자를 재배열하여 형성된 단어나 구문을 의미합니다.

 

 

Constraints

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

---

STEP 2. 'Group Anagrams' 코드(code)

 

■ Runtime: 87 ms Beats 68.95% of users with Python3
■ Memory: 19.36 MB Beats 94.69% of users with Python3

 

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        check_dict = dict()
        for s in strs:
            sorted_s = "".join(sorted(s))
            if sorted_s not in check_dict:
                check_dict[sorted_s] = [s]
            else:
                check_dict[sorted_s].append(s)
        return list(check_dict.values())

---

STEP 3. 'Group Anagrams' 해설

 

Hash & array로 문제를 접근했습니다. 애나그램은 본질적으로 동일한 단어의 순서만 다른 것이기에, sorted 함수를 적용하여 같은 문자열에 대해서는 dictioanry value list에 append 했습니다.

그리고 최종적으로 dicionary value를 list를 return 했습니다.

 

 

STEP 4. 'Group Anagrams' solution

 

추가적으로, Leetcode에서 제공해준 solution 코드를 살펴보겠습니다.

 

[코드 작성 결과, 속도, 데이터 점유율을 정리]

■ Runtime: 91 ms Beats 50.62% of users with Python3
■ Memory: 20.13 MB Beats 56.99% of users with Python3

 

from collections import defaultdict
class Solution(object):
    def groupAnagrams(self,strs):
        h= defaultdict(list)
        k=""
        for you in strs:
            s = k.join(sorted(you))
            h[s].append(you)
        return sorted(h.values())

 

위 방법도 동일하게 dictionary에 hash 함수를 적용해서 계산하지만, "from collections import defaultdict"를 적용해서 if else 구문을 처리했습니다.

---

■ 마무리

 

오늘은 Leetcode 알고리즘 문제 '49. Group Anagrams'에 대해서 알아봤습니다.

좋아요와 댓글 부탁드리며,

오늘 하루도 즐거운 날 되시길 기도하겠습니다 :)

감사합니다.