[Leetcode] 49. Group Anagrams - JS

https://leetcode.com/problems/group-anagrams/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
- 문자열 배열 strs가 주어질 때, 아나그램 그룹을 반환하라
- 반환할 때 순서는 상관없다.

제한조건
--------------------
- 1 <= strs.length <= 10^4
- 0 <= strs[i].length <= 100
- strs[i]는 영어 소문자로 구성된다.

 

2. 접근 방법

접근방법
--------------------
- anaGroup 객체를 선언한다.
- strs를 순회한다.
    - 각 문자열의 정렬하여 anaGroup의 key로 등록하고 해당 key의 값으로 배열에 원본을 추가한다.
- anaGroup의 값들을 반환한다.

 

 

3. 코드

var groupAnagrams = function(strs) {
    const anaGroup = {};

    for (let str of strs) {
        const sorted = [...str].sort().join('');
        if (!anaGroup[sorted]) {
            anaGroup[sorted] = [str]
        } else {
            anaGroup[sorted].push(str);
        }
    }
    return Object.values(anaGroup)
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n * m log m)

- 공간복잡도: O(n)

 

strs 배열 속의 문자열을 정렬한 값을 key 값으로 해쉬 맵을 구성했다.

sort 함수에 대한 보통의 시간 복잡도가 m * log m 이므도 n^2보다는 빠른 편에 속한다.