[LEET CODE] 49. Group Anagrams (dict 자료형, sort(), sorted())

# Problem

* anagram(애너그램) :  일종의 언어유희로 문자를 재배열하여 다른 뜻을 가진 단어로 바꾸는 것 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 lower-case English letters.

 

# My Answer

import collections
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
            answer = []
            answer_dict=collections.defaultdict() # dict 자료형 answer_dict 선언
            for word in strs:
                s_word =  "".join(sorted(word)) # 키로 사용하기 위하여 알파벳 순 정렬
                if s_word in answer_dict: # 이미 해당 키 존재할 경우 값 리스트에 추가하기
                    answer_dict[s_word].append(word)
                else:  # 해당 키가 없을 경우 새로운 키 - 값 리스트 생성
                    answer_dict[s_word] = []
                    answer_dict[s_word].append(word) # 값 리스트에 추가

            return answer_dict.values() # 값 반환 - 같은 알파벳들로 모인 리스트 반환

-> defaultdict(list)를 이용하여 처음에 지정 가능

 

# Solution 1 - 정렬하여 비교하기

import collections

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams = collections.defaultdict(list)

        for word in strs:
            # 정렬하여 딕셔너리에 추가
            anagrams[''.join(sorted(word))].append(word)
        return list(anagrams.values())

딕셔너리에서는 존재하지 않는 키를 삽입하려하면 KeyError 발생하므로 항상 디폴트를 생성해주는 defaultdict()로 선언 

---

# defaultdict()

 

collections 모듈의 defaultdict() - dict()의 서브클래스

인자로 받은 객체의 기본값으로 defaultdict의 기본값 지정 (int, list, set) 등

ex) defaultdict(list)

기본 값은 빈 리스트

import collections.defaultdict()

list_dict = defaultdict(list)
print(list_dict['a']) # []

# 값에 추가할 때
list_dict['a'].append(1)

print(list_dict) # defaultdict(<class 'list'>, {'a': [1]})

 

# 여러가지 정렬 방법

sort() / sorted() (newnuleee.tistory.com/2?category=1142686)

sort() - 리스트 자체를 정렬하는 제자리 정렬( In-place Sort) 

sorted() - 결과로 새로운 리스트를 반환

                 key 옵션을 지정해 정렬을 위한 키 또는 함수를 지정

a = ['abc','abcd','aa','b']
sorted(a,key=len)

# 함수 이용
def fn(s):
	retun s[0],s[-1]
sorted(a,key=fn)

# lambda 이용
sorted(a, key = lambda x:(x[0],x[-1]))

 

리스트는 join 함수 이용하여 문자열로 결합

"".join(sorted(a))