49. Group Anagrams

난이도: 중간 (Medium)

링크: LeetCode 49

풀이 날짜: 2025/10/21

 

1. 문제 이해

입력:

strs = ["eat","tea","tan","ate","nat","bat"]

출력:

[["eat","tea","ate"],["tan","nat"],["bat"]]

 

문자 순서를 재배열해서 동일한 단어가 될 수 있는 문자열들을 하나의 그룹으로 묶는다. 즉, Anagram(아나그램) 들을 함께 모으는 문제다.

 

2. 접근 방식 — 정렬된 문자열(Key) 기반 해싱

두 문자열이 아나그램인지 확인하는 가장 간단한 방법은 다음과 같다: 문자열의 문자를 정렬했을 때 동일한 결과를 갖는지 비교한다.

 

예를 들어

 

• "eat", "tea", "ate" → 모두 정렬 시 "aet"
• "tan", "nat" → 모두 정렬 시 "ant"

이 규칙을 활용하면, 정렬된 문자열을 해시맵의 키(key) 로 사용하여 동일한 그룹에 묶을 수 있다.

 

3. 풀이 코드

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
  const groupMap = {};

  for (const s of strs) {
    // 1.각 단어를 정렬하여 공통 키 생성
    const sorted = s.split('').sort().join('');

    // 2.해당 키가 없으면 새 그룹을 생성
    if (!groupMap[sorted]) {
      groupMap[sorted] = [];
    }

    // 3.동일 키에 단어 추가
    groupMap[sorted].push(s);
  }

  // 4.그룹들의 배열(map 의 값)만 반환
  return Object.values(groupMap);
};

구분	복잡도	설명
시간 복잡도	O(N × K log K)	N: 단어 개수, K: 단어 평균 길이 (정렬 과정)
공간 복잡도	O(N × K)	그룹 저장 공간

 

4. 핵심 정리

개념	설명
문제 유형	HashMap, String Manipulation
핵심 아이디어	정렬된 문자열을 키로 사용해 동일한 아나그램 그룹화
시간 복잡도	O(N × K log K)
공간 복잡도	O(N × K)
포인트	“정렬된 문자열이 같으면 같은 그룹이다.” — 간단하지만 강력한 패턴