[알고리즘] Leetcode #49 그룹 애너그램 (Python)

 

---

↓↓↓ 아래는 내 리트코드 계정 ↓↓↓

leetcode.com/Jiwon_Lee/

Jiwon Lee - LeetCode Profile

 

---

 

문제 설명

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.

 

입출력 예

Example 1:

Input	strs = ["eat","tea","tan","ate","nat","bat"]
Output	[["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

Input	strs = [""]
Output	[[""]]

Example 3:

Input	strs = ["a"]
Output	[["a"]]

 

Constraints

• 1 <= strs.length <= 104

• 0 <= strs[i].length <= 100

• strs[i] consists of lower-case English letters.

 

CODE

anagrams = collections.defaultdict(list)
for word in strs:
    # sort and append to dict
    anagrams[''.join(sorted(word))].append(word)

list(anagrams.values())

애너그램은 지난 번에 팰린드롬과 비슷하면서도 다른 개념인데, 문자의 순서를 바꿔서 다른 단어를 만드는 언어유희의 일종이라고 한다. 예를 들어, 위의 입/출력 예시처럼 'eat', 'ate', 'tea'는 모두 하나의 애너그램. 우선 애너그램끼리 그룹을 지어주기 위해, 정렬하여 같은 단어들끼리 묶어준다. 이를 위해 defaultdict를 하나 생성하고, 정렬된 단어(ex. 'aet')를 키로 하여 해당 값들을 리스트의 형태로 저장해준다.

마지막으로 defaultdict의 값들을 리스트로 변환해 return해주면 끝! 

+) python에는 정렬 기능을 수행하는 두 가지 메서드가 있다. 하나는 sorted() 함수로, 숫자 뿐 아니라 문자도 정렬이 가능하며, 정렬한 값을 바로 return한다. 더불어, key 옵션을 사용해 정렬의 기준을 직접 정해줄 수 있다. 반면, sort() 메소드는 in-place 정렬을 따르므로, 정렬 결과를 return해주지 않는다. (return 결과는 None)

 

---

 

 

I'm a Senior Student in Data Science ! 

데이터 사이언스를 공부하고 있는 학부생의 TIL 블로그입니다. 게시글이 도움 되셨다면 구독과 좋아요 :)