[LeetCode] 49. 그룹 애너그램(Group Anagrams)

문자열 배열을 받아 애너그램 단위로 그룹핑하라. 어떤 순서로든 답을 반환해도 된다.

 

1. 내가 직접 푼 코드

 

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        strs.sort(key=lambda x: sorted(x)) # 정렬된 str을 기준으로 줄 세우기
        output = list()
        output.append([strs[0]])
        strs.pop(0)
        i = 0
        # 앞의 str과 비교하여 애너그램이면 앞 str의 리스트에 추가, 그렇지 않으면 따로 리스트 생성
        for str in strs:
            if sorted(str) == sorted(output[i][0]):
                output[i].append(str)
            else:
                output.append([str])
                i = i+1
        return output

 

해설 :

 

입력받은 strs가 순서가 뒤죽박죽이기 때문에

우선 정렬을 시켰다(보통 정렬을 시켜놓고 문제를 푸는 것이 편하더라..).

그 후 그룹핑할 리스트인 output을 만들고

뒤의 반복문을 사용할 때 strs의 0번째 str은 비교할 대상이 없으니까 저런 식으로 미리 넣어두고 시작.

반복문에서 앞의 정렬된 str과 그 다음 정렬된 str을 비교하여

애너그램이면 같은 리스트에 넣고

앞선 str의 애너그램이 아니면 따로 리스트를 만든다.

 

 

 

 

** 깔끔한 답안 **

2. 정렬하여 딕셔너리에 추가

 

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)
        print(anagrams)
        return list(anagrams.values())

 

해설 :

 

기존의 딕셔너리는 존재하지 않는 key 값을 넣으면 error를 출력한다.

그래서 defaultdict를 생성했다!

이후 정렬한 값이 존재하면 그대로 넣어주고

존재하지 않으면 따로 생성해주고 넣어준다.

(너무 간단해서 놀랍다...)

마지막으로 key 값을 제외하고 출력해야 하므로 anagrams.value()를 써준다.

 

 

 

 

 

 

 

 

출처 : 파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]