“파이썬 알고리즘 인터뷰” + https://leetcode.com/problems/group-anagrams/
문자열 배열을 입력 받아 애너그램(anagram) 단위로 그루핑하는 문제. 애너그램은 단어 안에서 문자를 재배치 해서 다른 단어를 만드는 것을 말한다. 예를 들어 “tea”라는 단어의 배치를 바꿔 “ate” 또는 “eat”로 만드는 것.
입력이 [“eat”,”tea”,”tan”,”ate”,”nat”,”bat”]와 같은 문자열의 리스트로 주어지고, 출력은 [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]] 처럼 문자열 리스트의 리스트가 되어야 한다.
그냥 푼다고 생각하면 각 단어를 읽어서 정렬한 다음 정렬한 단어를 키로 하는 딕셔너리에 단어를 등록하고 딕셔너리의 값들(리스트들)을 리턴하면 되겠다. 그것을 파이썬 답게 적으면 다음과 같다.
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)
return anagrams.values()여기에서도 defaultdict가 사용됐다. 몇 번 사용해보니 정말 편한 걸? 그 외에 문자열 정렬에 sorted()를 사용한 정도일까.
책에 파이썬의 정렬 알고리즘에 대해서 설명하는 부분이 있는데 흥미로웠다. 퀵소트(quick sort)니 머지소트(merge sort)니 이름만 들었고 평소에 직접 정렬 기능을 사용할 일이 거의 없어서 중요하다는 것을 알면서도 알지 못했던 것들이다. 너무 슬프다. 학부에서 공부할 때는 원시적?인 정렬 알고리즘까지 하나 씩 다 구현 해보면서 익혔는데 이젠 실무에서 뭐가 사용되는지도 모르고 산다니… 아무튼, 일반적으로 퀵소트가 쓰이고 대부분의 상황에서 가장 빠르다는 정도는 안다. 하지만 퀵소트는 최악의 상황에서 복잡도가 O(n^2)이므로 데이터 정렬 상태가 들쑥날쑥 하다면 어느 상황에서든 O(n log n)인 머지소트를 사용하는 것도 좋다.
그런데 최근 파이썬은 팀소트(Tim sort)라는 팀 피터스(Tim Peters)가 머지소트를 베이스로 만든 알고리즘이 널리 쓰인다고 한다. 팀소트는 주어진 데이터가 대부분 정렬되어 있을 것이라고 가정하고 정렬하기 때문에, 최선의 상황에서 복잡도가 O(n)이라고 한다. 파이썬의 sorted()는 이 팀소트를 사용하고 있고 자바에서도 포팅해 쓸 정도로 효율적인 알고리즘이다. 정렬 기능 쓰면서 이런 것까지 따지는 경우가 잘 있진 않겠지만 깊이 공부할 수 있으면 좋겠다.