본문 바로가기
개발/알고리즘

[Leetcode]49. Group Anagrams 문제 풀이

by ISA(류) 2021. 6. 26.

# 문제 원문

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: [[""]]

# 문제풀이

동일한 str를 가진 아나그램들을 찾는 문제다. 아나그램 자체가 동일한 문자들을 순서를 다르게 한 문자열을 지칭하는 용어에 해당하니 결국 무작위 문자열중 동일한 문자들로 구성된 문자열들을 배열로 묶어서 리턴해주면 되는 문제. 여기서 동일한 문자로 구성된 것을 어떻게 찾을 것이냐? 라는게 핵심인 문제로 문제 자체의 해결보다는 어떤 방법들로 문제를 해결하냐가 중요한 문제가 아닐까 생각이 들었다. 미디움 난이도지만 실제 풀이 자체는 쉬워서인지 현시점에서 통과율은 60프로 이상인 문제이다.

기본적인 자료구조인 맵과 객체를 이용한 방식으로 2가지 사용해서 풀어봤고, 사실상 로직상의 차이는 없다.

## 솔루션 플로우

1. INPUT으로 들어온 strs를 최소 1회 순환해서 판별한다.
2. 각 strs의 원소인 str 문자열을 배열로 쪼갠후 정렬 해준후 합친다.
3. 정렬 된 동일 아나그램 문자열들은 결국 같은 문자열이 되므로 동일한 문자열들의 원본을 result 배열에 배열로 분리해서 넣어준다.
4. 얻은 result를 리턴해주면 끝난다.

1. 기본적인 객체를 이용한 풀이

const groupAnagrams = function (strs) {
    const result = {};

    strs.forEach((str) => {
        const state = str.split('').sort().join();
        if (result[state] === undefined) {
            result[state] = [];
        }
        result[state].push(str);
    });

    return Object.values(result);
};
/**
 * Runtime: 136 ms, faster than 65.91% of JavaScript online submissions for Group Anagrams.
 * Memory Usage: 50.7 MB, less than 28.73% of JavaScript online submissions for Group Anagrams.
 */

2. 맵을 이용한 풀이

const groupAnagrams = function (strs) {
    const result = new Map();

    strs.forEach((str) => {
        const state = str.split('').sort().join();
        if (!result.has(state)) {
            result.set(state, []);
        }
        result.get(state).push(str);
    });

    return Array.from(result.values());
};
/**
 * Runtime: 116 ms, faster than 97.70% of JavaScript online submissions for Group Anagrams.
 * Memory Usage: 49.7 MB, less than 63.52% of JavaScript online submissions for Group Anagrams.
 */

 

반응형