[LeetCode] 리트코드 49. Group Anagrams(JS)

문제

Group Anagrams - LeetCode

- 난이도 Medium

- 관련 주제: Hast Table, String

 

문제 설명

Group Anagrams 문제 설명

 strs 라는 string들로 이루어진 배열이 주어질 때 anagram이 되는 것들을 함께 grouping 하는 문제. 정답은 어떤 순서에 상관없이 return 해도 된다.

 Anagram은 일반적으로 기존의 단어들을 정확히 한번만 모두 사용하여 해당 단어들을 재배열해서 다른 단어 또는 문구를 만든 단어 또는 문구를 의미한다.

 

즉 tree 가 있으면 etre, eetr, eert, tere 등의 단어들이 모두 tree에 포함되는 단어 각각을 한번씩 그리고 모두 사용하였기 때문에 해당 단어들은 tree의 Anagram이 되는 것이다.

 

해결 방법

먼저 각 string을 각 알파벳별로 분리시킨 다음 알파벳순으로 정렬 후 다시 합쳐주어 모든 string 값들이 동등한 모습을 하도록 setting한다. 이후 Hash Table을 이용하여 동등한 string이 있는지 여부를 확인해주면서 변환 전 기존 string 값을 hash table에 넣어주는 식으로 Anagram 판별

 

- 배열에 존재하는 string이 1개 또는 비어있는 경우 해당 부분만 출력

- 나머지 부분은 모두 알파벳 순으로 string을 정렬

- 정렬 후 hash table을 이용

   - has() 로 anagram 여부 확인

      - 있으면 set() 으로 해당 string 포함하여 기존 hash table 복사하며 다시 hast table에 넣기

      - 없으면 set()으로 새로 세팅해주기

- 마지막으로 result 배열을 만들어 result 배열에 모든 hash table 값들 넣고 return 하기

 

Code

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    const leng = strs.length;
    const setA = new Map();
    
    if(leng === 1)
        return [strs];
    
    for(let i = 0; i < leng; i++) {
        let tmp = strs[i].split("").sort().join(""); // string을 알파벳별로 쪼갠 다음 정렬해서 다시 합치기
        if(setA.has(tmp)) // map에 있는지 확인
            setA.set(tmp,[...setA.get(tmp), strs[i]]); // 문자열 합치는 ... operator
        else // 없는 경우
            setA.set(tmp,[strs[i]]); // 세팅해주기
    }
    
    const result = []; // 결과 담는 배열 
    
    for(let a of setA.values()) {
        result.push(a);
    }
    return result;
};

 

정답 캡쳐 화면