[LeatCode] Medium 49 Group Anagrams (Java)

문제 링크

https://leetcode.com/problems/group-anagrams/description/

풀이

1. 접근 방법

문제 정의

• 아나그램(Anagram): 특정 문자열의 모든 문자를 재배열하여 만든 문자열

제약 사항

• 문자열 배열의 크기: 1 <= strs.length <= 10^4
• 비효율적 방법: 2중 for문을 통한 완전 탐색은 시간 초과 가능성이 높음

해결 아이디어

• 정렬 후 비교:
  • 아나그램 문자열은 알파벳을 정렬하면 동일한 문자열을 생성
  • 예: "eat", "tea", "ate" → 정렬 결과: "aet"
• 각 문자열의 정렬 결과를 키(Key)로 사용해 그룹화

효율적인 데이터 구조: HashMap

• Key: 정렬한 문자열
• Value: 해당 키에 속하는 원본 문자열 리스트
• HashMap은 상수 시간 검색(O(1))이 가능하여 효율적임

2. 의사 코드

map = 빈 HashMap (key: 정렬된 문자열, value: 문자열 리스트)

for str in strs:
    charArray = str의 문자 배열
    정렬(charArray)

    sortedStr = charArray를 문자열로 변환

    if sortedStr가 map에 없으면:
        map[sortedStr] = 빈 리스트

    map[sortedStr].add(str)

answer = 빈 리스트
for value in map의 모든 값:
    answer.add(value)

return answer

3. 시간 복잡도

• 문자열 배열 순회와 정렬이 주요 소요 시간
• O(N × K log K)
• 1 <= N <= 10^4 (문자열 배열의 길이)
• 0 <= K <= 100 (각 문자열의 길이)

4. 구현

import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {

        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] charArray = str.toCharArray();
            Arrays.sort(charArray);
            String string = String.valueOf(charArray);
            if (!map.containsKey(string)) {
                map.put(string, new ArrayList<>());
            }
            List<String> list = map.get(string);
            list.add(str);
            map.put(string, list);
        }

        List<List<String>> answer = new ArrayList<>();
        for (String key : map.keySet()) {
            answer.add(map.get(key));
        }

        return answer;
    }
}