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 <= 10^4 0 <= strs[i].length <= 100 strs[i] consists of lowercase English letters.
문제 이해 (사고의 흐름)
1. 각 string을 정렬해서 같은 것이 같은 애나그룹이겠다.
2. 그렇게 정렬된 strs에서 같은 문자열을 가진 것의 index의 strs[index]끼리 새 group 배열에 append해주고,
3. 최종 결과 배열에 그렇게 모은 group 배열을 append 해주면 끝 이지 않을까?
첫 번째 풀이
import collections
from typing import List
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
sorted_strs = [''.join(sorted(s)) for s in strs]
d = collections.defaultdict(list)
for inx, word in enumerate(sorted_strs):
d[word].append(inx)
result = []
for key in d:
group = []
for inx in d[key]:
group.append(strs[inx])
result.append(group)
return result
더 python 스럽게
import collections
from typing import List
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
d = collections.defaultdict(list)
for word in strs:
d[''.join(sorted(word))].append(word)
return list(d.values())
파이썬 sorted()의 정렬 방식 - Timsort
Timsort란 '실제 데이터는 대부분 이미 정렬되어 있을 것이다'라고 가정하고 실제 데이터에서 고성능을 낼 수 있도록 설계한 알고리즘으로,
개별적인 단일 알고리즘이 아니라 삽입 정렬과 병합 정렬을 휴리스틱하게 적절히 조합해 사용하는 정렬 알고리즘이다.
정렬이 필요한 대부분의 경우와 별다른 제약사항이 없는 온라인 코딩 테스트시에는 python의 내장 정렬함수를 사용하는 것이 가장 빠르다. 이유는
1. 실제 데이터에 적합한 Tim sort를 사용해서 구현되었고,
2. 파이썬의 내장 함수로서 CPython는 C언어를 이용해 작성되었기 때문이다.
Tim sort의 시간복잡도가 어떻게 되길래 일반적인 실행 속도가 빠르다는 것인지 알아보자.
시간복잡도가 O(n log n)인 정렬 알고리즘이 있다고 하자. 이 말은 실제 동작 시간은 C×nlogn+α 라는 말이다. 여기서 실제 동작 시간에 큰 영향을 끼치는 것은 C 값이며, C 값에 영향을 주는 요소는 '알고리즘이 참조 지역성(Locality of reference) 원리를 얼마나 잘 만족하는가'이다.
여기서 궁금한 것이 생긴다.
1. 참조 지역성 원리는 뭘까?
2. 참조 지역성 원리를 잘 만족한다는 것이 C의 값에 어떻게 영향을 미칠까?
3. Tim sort의 원리에 따른 참조 지역성과 시간 복잡도는 어떻게 될까?
1. 참조 지역성 원리는 뭘까?
참조 지역성 원리란, CPU가 미래에 원하는 데이터를 예측하여 속도가 빠른 장치인 캐시 메모리에 담아 놓는데 이때의 예측률을 높이기 위하여 사용하는 원리이다. 쉽게 말하자면, 최근에 참조한 메모리나 그 메모리와 인접한 메모리를 다시 참조할 확률이 높다는 이론을 기반으로 캐시 메모리에 담아놓는 것이다.
2. 참조 지역성 원리를 잘 만족한다는 것이 C의 값에 어떻게 영향을 미칠까?
메모리를 연속으로 읽는 작업은 캐시 메모리에서 읽어오기에 빠른 반면, 무작위로 읽는 작업은 메인 메모리에서 읽어오기에 속도의 차이가 있다.
Insertion Sort의 참조 지역성)
이미지 출처: https://bit.ly/3m0pduf
Insertion Sort의 시간복잡도는 평균 O(n^2), 최악의 경우 O(n^2)로 별로 좋지 않다. 그러나 참조 지역성 측면에서는 인접한 메모리와의 비교를 반복하기에 참조 지역성의 원리를 매우 잘 만족하고 있는 것을 확인할 수 있다.
Merge sort의 참조 지역성)
이미지 출처: https://bit.ly/3m0pduf
Merge sort의 시간복잡도는 평균 O(n log n), 최악의 경우 O(n log n)이고, 인접한 덩어리를 병합하기에 참조 지역성의 원리를 어느 정도 잘 만족한다. 그러나 입력 배열 크기만큼의 메모리를 추가로 사용한다는 단점이 있다.
3. Tim sort의 원리에 따른 참조 지역성과 시간 복잡도는 어떻게 될까?
Timsort의 시간 복잡도에서 최선은 O(n), 평균은 O(nlogn), 최악의 경우 시간 복잡도는 O(nlogn)이다.
구체적으로 Tim sort의 원리를 보며 시간복잡도를 생각해보자면,,
삽입 정렬과 병합 정렬을 휴리스틱하게 적절히 조합해 사용하는 정렬 알고리즘인 Tim sort는
1. merge sort에서처럼 전체를 작은 덩어리로 자르고,
2. 각각의 덩어리를 Insertion sort로 정렬한 뒤,
3. merge sort에서 병합하는 것 처럼 병합하면 좀 더 빠르지 않을까 하는 것이 기본적인 아이디어이다.
2^x개씩 잘라 각각을 Insertion sort로 정렬하면 일반적인 Merge sort보다 덩어리별x개의 병합 동작이 생략되어,
Merge sort의 동작 시간을 Cm×nlogn이라 할 때, 각 분할 별 병합하는 시간인 Cmxn 시간이 빠지니까
Tim sort의 동작 시간은Cm×n(logn−x)+α가 된다.
이때의x값을 최대한 크게 하고α 값을 최대한 줄이기 위해 여러 가지 최적화 기법이 사용된다.
4. Tim sort의 최적화 기법
1) Run
2^x개씩 잘라 각각을 Insertion sort로 정렬한다고 할 때 Insertion sort가 필요없는 부분은 sort를 진행하지 않고 덩어리를 최대한 크게 만들어 병합 횟수를 최대한 줄이는 것이다.
이미지 출처: Naver D2 <Tim sort에 대해 알아보자>
이 배열을 2^2 개씩 덩어리로 자른다고 가정해보자.
앞의 10, 13을 봤을 때 증가하는 원소가 있는 덩어리라고 생각하고 2^2 개가 될 때까지 뒤의 원소들을 추가로 insertion sort가 되어야 한다. 그럼 결과적으로 [9, 10, 13, 15] 가 될 것이다.
여기서 멈추지 않고 최대한 덩어리 x를 크게 만들어야 하므로 뒤의 원소 또한 증가한다면 이 덩어리에 포함시킨다. 이 배열에서 [18,21]의 경우 이어지는 증가하는 원소들이므로 같은 덩어리로 묶는다.
그런데 18, 21은 이미 정렬이 되어 있으므로 Insertion sort가 필요없는 부분이니까 insertion sort를 사용하지 않고 앞의 원소와 대소만 비교해서 덩어리로 묶는다.
그 다음은 13이다. 13은 증가하는 원소와 연관이 없으니 새로운 덩어리로 묶는다. (여기서 덩어리의 크기는 제각각(run의 길이가 제각각)이 된다는 것을 알 수 있다.)
13, 8을 보니 감소하는 원소가 있는 덩어리이다. 2^2 개가 될 때까지 뒤의 원소들을 추가로 insertion sort가 되어야 한다. 그럼 결과적으로 [13, 11, 8, 5] 가 될 것이다.
여기서 멈추지 않고 최대한 덩어리 x를 크게 만들어야 하므로 뒤의 원소 또한 감소한다면 이 덩어리에 포함시킨다. 이 배열에서 [3]의 경우 이어지는 감소하는 원소들이 될 수 있으므로 같은 덩어리로 묶는다.
이후 감소하는 run은 뒤집어서 모든 run이 증가하는 run이 되도록 변환한다.
정리하면 덩어리의 첫 두 원소의 대소 관계로 이 덩어리를 증가하는 덩어리, 감소하는 덩어리로 정의하여 2^x개까지는 Insertion sort를 진행하고 그 이후의 원소에 대해서 가능한 한 크게 덩어리를 만든다. 이런 덩어리를 run이라고 부르며 2^x개라는 기준에 해당하는 것이 minrun이다.
이쯤에서 앞서 Timsort란 '실제 데이터는 대부분 이미 정렬되어 있을 것이다'라고 가정해서 설계한 알고리즘이라는 걸 떠올려보자면 완전한 무작위가 아닌 실생활에 가까운 데이터는 특성상 약간의 증가/감소 정렬이 있을 것이고 이를 최대한 활용하여 덩어리(run)을 크게 만들기위해 삽입 정렬과 병합 정렬을 휴리스틱하게 적절히 조합해 사용하는 정렬 알고리즘 이라는게 조금은 더 와닿는다.
2) Merge
앞서 run을 최대한 크게 만들었다. 이제 효율적인 방법으로 run들을 병합할 차례이다.
2-1) 먼저 비슷한 크기의 두 run 알아내기
앞서 run을 만들 때도 느꼈지만 여기서 덩어리의 크기는 제각각(run의 길이가 제각각)이 된다. 이럴 경우 어떻게 하면 비슷한 크기의 덩어리끼리 병합하도록 구현할 수 있을까?
이미지 출처: Naver D2 <Tim sort에 대해 알아보자>
Tim sort에서는 하나의 run이 만들어질 때마다 스택에 담는데, run을 스택에 push할 때마다 스택의 맨 위의 세 run (위의 그림에서 A, B, C) 이 위의 그림과 같이 두 조건을 만족해야 한다.
만족하지 않으면 위의 조건이 만족될 때까지 B는 A와 C 중 작은 run과 병합한다.
2-2) 병합할 두 run을 알아냈으니 (기존의 merge sort의 단점인)추가 메모리 사용없이 병합하기
merge sort에서는 병합하는 과정에서 추가 메모리와 병합할 두 덩어리 크기 합만큼 시간이 소요된다.
그런데 아래의 방법을 사용하면 두 run 중 크기가 작은 run을 담을 추가 메모리만 필요해진다. 최악의 경우라도 추가 메모리 절반 O(n/2) 을 절약할 수 있는 것이다.
이미지 출처: Naver D2 <Tim sort에 대해 알아보자>
이렇게 이웃한 초록색 run A와 빨간색 run B을 하나의 run으로 병합하는 과정을 보여준다. 먼저 병합하기 전 두 개의 run 중 크기가 더 작은 run인 A를 복사한다. 이후 각 run의 시작 부분부터 크기 비교를 하여 작은 순서대로 앞을 채우면서 병합을 진행한다.
그리고 추가로 추가의 시간 O(log k)가 들더라도 이분 탐색을 통해 이미 정렬과 병합이 잘 되어있어 비교 시간과 추가 메모리가 필요 없는 run 구간이 뭔지 알아내는 최적화가 진행된다.
3) Galloping
병합시 Galloping 이라는 기법도 최적화를 위해 사용된다고 한다.
이 부분은 아직 잘 이해가 되지 않아서 Naver D2 글에 나와있는 전문을 그대로 가져왔다.
이미지 출처: Naver D2 <Tim sort에 대해 알아보자>
위는 이웃한 두 run을 병합하는 과정 중 일부를 잘라 표현한 그림이다. 초록색으로 색칠되어 있는 부분은 run A의 일부, 빨간색으로 색칠되어 있는 부분은 run B의 일부이다. 처음에는 화살표가 가리키고 있는 두 원소를 대소 비교를 하여 어느 run의 원소를 넣을지 정한다. 이 때의 방법을 One pair at a time mode라 칭한다. 이때 run B의 원소가 33번 연속으로 병합되었기에 Galloping mode로 전환된다. 이 모드에서는 1, 2, 4, 8, ...과 같이 2^k2 k 로 뛰어 넘으며 대소 비교를 진행한다. 위의 그림에서는 10, 30, 7510,30,75와 비교하는 것을 알 수 있다. 7575와 비교하면 70 \lt 75이므로 [45,50,60,75]의 범위에서 이분 탐색을 진행하여 어느 위치까지 병합할지 결정한다. 이후 다시 하나의 run에서 연속적으로 병합되지 않을 경우 One pair at a time mode로 돌아가 다시 하나씩 비교를 진행한다. 실제 코드에서는 MIN_GALLOP번 연속으로 한 run에서 병합되었을 경우 Galloping mode로 전환하며 MIN_GALLOP는 전체 배열을 정렬하는 과정에서 Galloping mode에 들어가는 횟수가 많았다면 감소하고 아니라면 증가하여 좀 더 효율적으로 동작하도록 진행한다.
지금까지 python의 sorted() 정렬 알고리즘인 Tim sort에 대해서 알게 된 것을 나름대로 정리해보았다.
현재 Tim sort는 Python, Java 7의 공식 정렬 알고리즘, Google chrome(V8), swift 등에서 활용되고 있다.
Go 에서는 위에서 <병합> 부분에서 나온 것 처럼 추가 메모리 절반 O(n/2)이 필요하다는 점에서 공간 복잡도상 도입을 거절했다고 한다.
