Leetcode 49. Group Anagrams

문제 개요

단어들의 배열 words가 주어진다. words안에 있는 단어들을 같은 anagram으로 묶은 결과를 반환해야 한다.

anagram이란 단어를 구성하는 문자들이 같은 관계를 의미한다.

예를 들어 bat 과 tab은 단어 a,b,t로 구성되어있으며 단어의 위치가 다른 anagram 관계라고 볼 수 있다.

예시

words = ["eat","tea","tan","ate","nat","bat"] 일 groupAnagrams의 결과 값은

group_anagram = [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']] 이다.

문제 분석

두 단어가 anagram인지 확인하기 위해선 각 단어들이 이루고 있는 문자가 똑같은지 확인해야 한다.

또한, group을 생성하기 위해 처음으로 나온 anagram group인지 기존에 존재하는 group인지 확인하기 위한 전략을 세워야 한다.

해결 전략

문자가 똑같다면 각 문자들을 정렬한 결과값은 항상 동일할 것이다.

bat, tab을 알파뱃 순으로 정렬하면 abt가 나오며, 이를 이용해 anagram group을 만들 수 있다.

또한, 그룹을 생성할 때, 기존에 없는 그룹일 경우 새로 list를 생성하여 추가할 수 있도록 collections라이브러리의 defaultdict을 이용할 수 있다.

코드를 작성하면 아래와 같다.

from typing import List

def groupAnagram(words: List[str]) -> List[List[str]]:
    group = defaultdict(list)
    for word in words:
        ## 알파뱃 순으로 정렬하면 group을 구분할 key가 생성된다.
        key = "".join(sorted(word))

        ## key에 대한 group이 없더라도, defaultdict에서 빈 리스트([])를 생성해준다.
        group[key].append(word)

    ## group의 값만 반환해준다.
    return group.values()

#coding-interview #sorting

Comments