[LeetCode 49] Group Anagrams (with Python / 문자열)

문제링크

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

Group Anagrams - LeetCode

문제설명

 

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.

 

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"]]

 

Constraints:

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

문제풀이

 

처음에 문제를 보고 떠오른 아이디어가

각 아이템의 문자열을 정렬을 해서 비교하는 문제이려나 하는 막연한 생각이 들었다.

하지만 그럼 소트 메소드를 쓰면 nlogn인데 for문 안에서 돌려야하니 시간복잡도가 n^2logn 이잖아?.. 하고 과감히 버렸던 아이디어 였지만,

 

고민끝에 답이 나오지않아 검색한 결과

1. 각 item의 문자열을 정렬하고 => 아나그램이라면 정렬한 문자열이 서로 같을테니까

2. 딕셔너리를 활용.

    { 아나그램: 문자열 } 형태로 삽입한다.

3. 딕셔너리 값들을 정답 리스트에 삽입

 하는 로직으로 구현하면 된다.

 

코드

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        myDict = {}
        answer = []

        for item in strs:
            anagram = "".join(sorted(item))
            if anagram not in myDict:
                myDict[anagram] = [item]
            else:
                myDict[anagram].append(item)

        for item in myDict:
            answer.append(myDict[item])

        return answer

        # 1. 각 알파벳들을 쪼개서 정렬
        # 2. {애너그램: 원래문자열} 형태로 딕셔너리 삽입
        # 3. 같이 묶여있는 값들 리스트에 삽입 => 리스트 형태로 출력해야하므로