Python 알고리즘 인터뷰 - 문제5 그룹 애너그램

leetcode 49. Group Anagrams

 

문자열 배열을 받아 애너그램 단위로 그룹핑하라

 

예제

입력

['eat', 'tea', 'tan', 'ate', 'nat', 'bat']

 

출력

[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

 

풀이

정렬된 word를 key로, word 리스트를 value로 하는 dict에 값을 저장하여 그룹핑한다. key에 해당하는 word가 존재할 시 word를 딕셔너리에 append한다. 여기서 일반 dict를 사용할 경우 존재하지 않는 key에 접근 시 에러가 발생하므로 'list' 타입의 기본값으로 value를 초기화 시켜주는 collections.defaultdict(list)를 사용한다. 

sorted함수는 리스트 형태로 값을 반환한다. s = 'abc'일 경우 sorted(s) = ['a','b','c'] 형태가 된다. 이를 문자열로 변경시키려면 ''.join 함수를 사용한다.

d = collections.defaultdict(list)
for word in words:
	key = ''.join(sorted(word))
    d[key].append(word)

 

d.values()는 dict_values 타입으로 값들을 반환하는데 list(d.values())로 묶어주면 list 타입으로 변환이 가능하다. 해당 값을 반환하도록 한다.

return list(d.values())

 

전체 코드

def groupAnagrams(inputs: list[str]):
    d = collections.defaultdict(list)
    for input in inputs:
        key = ''.join(sorted(input))
        d[key].append(input)

    return list(d.values())