[파이썬 알고리즘 인터뷰] 문자열 조작 - 그룹 애너그램

파이썬 알고리즘 인터뷰라는 책을 보는데 풀이만 보는 것보다 일단 엉망으로라도 풀어보고 풀이를 보는 것이 좋을거같아 정리한다.

🐍 문제

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

애너그램 : 문자를 재배열하여 다른 뜻을 가진 단어로 바꾸는 것
ex) 문전박대 -> 대박전문

• 입력
  ["eat", "tea", "tan", "ate", "nat", "bat"]
• 출력
  [ ["ate", "eat", "tea"], ["nat", "tan"], ["bat"] ]

🐍 내 풀이

결국은 동일한 문자를 사용했다는 점을 이용하여 문자열 재정렬 후 정렬한 문자열과 동일한지 비교하여 애너그램이 가능한지 판단하였다. 동일한 문자끼리 리스트에 묶어 원하는 출력 형태로 정리하였다. 출력 리스트에서 따로 정렬해야 한다는 조건이 없어 그대로 출력하였다.

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

# 입력받은 문자열을 sorted함수를 이용해 정렬
input_dict = dict()
for string in input_list:
	input_dict[string] = "".join(sorted(string))
# input_dict : {'eat': 'aet', 'tea': 'aet', 'tan': 'ant', 'ate': 'aet', 'nat': 'ant', 'bat': 'abt'}
    
output_dict = dict()
for ori_string, sort_string in input_dict.items():
	if sort_string in output_dict.keys():
		output_dict[sort_string].append(ori_string)
	else:
		output_dict[sort_string] = [ori_string]
# output_dict : {'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat'], 'abt': ['bat']}

answer = list(output_dict.values())
# answer : [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

🐍 교재 풀이

방식은 동일하나 코드가 더 간결하다. 애너그램 단위로 모은 딕셔너리에 문자열을 삽입할 때 키값이 존재하는지 판단하는 과정을 줄이기 위해 collections의 defaultdict를 이용하였다. defaultdict를 사용함으로써 for문 하나를 줄일 수 있었다.

import collections

def groupAnagrams(strs):
	anagrams = collections.defaultdict(list)
	for word in strs:
		anagrams[''.join(sorted(word))].append(word)
	return list(anagrams.values())
    
input_list = ['eat', 'tea', 'tan', 'ate', 'nat', 'bat']
groupAnagrams(input_list)
# [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]