49. 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.

 

 

풀이

 

전에 배웠던 아나그램, 동일한 원소로 이루어져있는 문자열을 아나그램이라고 한다.

 

사실 해시테이블을 통해서 만들 수도 있지만. 정렬과 set을 통해서 만들어봤다 ( set도 해시함수를 사용한다는걸 처음알았다)

 

 

리스트를 map함수를 통해 정렬시키고, 

class Solution(object):
    def groupAnagrams(self, strs):

        sort_list = list(map(sorted,strs))  # 각 원소 sorted 사용 (시간복잡도 폭발)


        strs_set = set()	# set에 각 값을 넣어 아나그램 개수 확인
        for i in sort_list:
            s = ''.join(i)			
            strs_set.add(s)
        
        result= [[] for __ in range(len(strs_set))]	# set저장된 원소의 개수만큼 정답리스트 생성

        strs_list = list(strs_set)	#index를 사용하기 위해 리스트 변환

        for i in range(len(sort_list)):	#strs리스트 순회
            result[strs_list.index(''.join(sort_list[i]))].append(strs[i])
       	#str_list 의 인덱스에 존재하는지 확인후 각 인덱스에 매핑되는 result인덱스 위치에 삽입
        return result

 

 

sorted함수를 사용하고 index함수까지 사용해서 시간복잡도가 높다..

 

 

 

다른사람의 코드 

 

from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        letters_to_words = defaultdict(list)
        for word in strs:
            letters_to_words[tuple(sorted(word))].append(word)
        return list(letters_to_words.values())

 

아..그냥 defaultdict를 생성해서 순서를 넣어서 나가면 되는구나..ㅎㅎ.. 비슷한 방법이지만 속도가 빠르고 코드도 간단하다.  

딕셔너리에 리스트를 기본으로 밸류로 매핑되게 만들어준 후 , 각 문자열을 정렬 시킨 후, 정렬시킨 값을 키로 딕셔너리에 넣고 마지막에 list로 값을 변경시켜서 나가면 된다.