.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
문자열 배열을 받아 애너그램 단위로 그룹핑하라.
My solution
그룹 애너그램을 하기 위해서 애너그램인 단어들은 정렬을 통해 같은단어로 만들어 비교한다.
모든 단어는 원래 그대로 유지되어야 하므로 for문을 돌면서 해시맵과 비슷한 형식의 객체의 값에 배열로 저장한다음 Object.values로 그 값들을 리턴한다.
Code
const groupAnagrams = function (s) {
const map = {};
for (const x of s) {
const word = x.split('').sort().join('');
if (map[word]) {
map[word] = [...map[word], x].sort();
} else {
map[word] = [x];
}
}
return Object.values(map);
};
JavaScript
복사
1. 정렬하여 딕셔너리에 추가
애너그램을 판단하는 가장 간단한 방법이 정렬하는 방법이다.
같은 방식의 풀이다.
파이썬의 정렬
sorted()와 sort()를 제공한다. sort()는 리스트에 제공되는데 제자리 정렬(In-place sort)이다. 입력을 출력으로 덮어 쓰기 때문에 별도의 추가 공간이 필요하지 않으며 리턴값이 없다.
sorted()는 결과를 리턴해준다.
팀소트는 파이썬에서 시작했다.
정렬 알고리즘과 팀소트
폰 노이만의 병합 정렬(Merge sort)은 Stable sort로 인기가 많다.
팀소트는 실제 데이터가 대부분 이미 정렬되어있다는 가정으로 고성능을 위해 설계되었다. 삽입 정렬과 병합 정렬을 휴리스틱하게 조합한 알고리즘이다.
파이썬 정렬함수는 대부분 가장 빠르고 자바에 영향을 줬고 Go는 병합정렬의 O(1/2n) 메모리 공간 때문에 팀소트를 거절했다.
한 번 이상 비교하면 O(nlogn)보다 빨라질 수 없지만 팀소트는 정렬되어 있을 때 비교를 건너뛰므로 O(n)이 가능하다.
