[LeetCode] 49. Group Anagrams 풀이 (Java)

✔️ 오늘의 리트코드 공부 기록 – Group Anagrams

---

문제 요약 (Group Anagrams)

문자열 배열이 주어질 때,
서로 애너그램(anagram) 관계에 있는 문자열끼리 묶어 반환하는 문제이다.

애너그램이란
→ 문자 구성은 같지만 순서만 다른 문자열
(예: "eat", "tea", "ate")

반환 순서는 상관없다.


문제 링크:
https://leetcode.com/problems/group-anagrams

---

🤔 처음 떠올린 아이디어

문제를 처음 봤을 때 이렇게 생각했다.

애너그램이면 결국 같은 문자들로 구성된 거잖아?
그럼 중요한 건 문자열의 순서가 아니라 구성이다.

그래서 자연스럽게 떠오른 생각은 이거였다.

문자열을 모두 정렬하면, 애너그램들은 모두 같은 형태가 되지 않을까?

예를 들면,

"eat" → "aet"
"tea" → "aet"
"ate" → "aet"


👉 정렬된 결과가 같으면 같은 그룹

이 아이디어를 기준으로 문제를 풀기로 했다.

---

💡 핵심 아이디어: 정렬된 문자열을 key로 사용

정리하면 접근은 이렇다.

1. 각 문자열을 정렬한다
2. 정렬된 문자열을 Map의 key로 사용한다.
3. 같은 key를 가진 문자열들을 하나의 리스트로 묶는다.

즉,

"aet" → ["eat", "tea", "ate"]
"ant" → ["tan", "nat"]

---

🧠 Map 설계에서 고민했던 포인트

여기서 잠깐 고민이 있었다.

key가 이미 Map에 있으면 add,
없으면 새 리스트를 만들어야 하는데,
이걸 어떻게 깔끔하게 처리할까?

처음 떠올린 방식

if (map.containsKey(key)) {
    map.get(key).add(value);
} else {
    List<String> list = new ArrayList<>();
    list.add(value);
    map.put(key, list);
}

동작은 맞지만, 코드가 조금 지저분하다.

✅ 더 깔끔한 방법: computeIfAbsent

이게 기억이 안나서 chatGPT한테 물어봤다.

map.computeIfAbsent(key, k -> new ArrayList<>()).add(value);

이 한 줄이 의미하는 건,
key가 있으면 → 기존 리스트 반환
key가 없으면 → 새 리스트 생성 후 put
그리고 바로 현재 값 add

---

🧩 문자열 정렬은 어떻게 할까?

Java에는 String.sort() 같은 메서드는 없다.
그래서 보통 아래 방식으로 정렬한다.
(이것도 기억이 안나서 물어봄..)

private String sortString(String s) {
    char[] arr = s.toCharArray();
    Arrays.sort(arr);
    return new String(arr);
}

---

코드 (Java) – 정렬 기반 풀이

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();

        for (String s : strs) {
            String key = sortString(s);
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }

        return new ArrayList<>(map.values());
    }

    private String sortString(String s) {
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        return new String(arr);
    }
}

---

🔹 두 번째 방법: 문자 빈도 배열을 key로 사용하기

문제를 풀고 나서 보니,
정렬조차 하지 않는 방법도 있다는 걸 알게 됐다.


대신 각 알파벳의 개수(26칸 배열)를 센다
즉, 같은 빈도 배열 → 같은 애너그램


예를 들어 "eat"은
a:1, e:1, t:1, 나머지:0

이 빈도 정보를 문자열로 직렬화해서 key로 사용한다.

---

이 방법은 정렬보다 시간복잡도에 있어서 더 우위에 있다.

• 정렬: O(k log k)
• 빈도 배열: O(k)

👉 문자열 길이가 길수록 더 효율적

---

빈도 배열 방식 코드 (Java)

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();

        for (String s : strs) {
            int[] count = new int[26];
            for (char c : s.toCharArray()) {
                count[c - 'a']++;
            }

            String key = Arrays.toString(count);
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }

        return new ArrayList<>(map.values());
    }
}

📈 시간 / 공간 복잡도

n: 문자열 개수
k: 문자열 길이

• 정렬 기반
• 시간복잡도: O(n · k log k)
• 공간복잡도: O(n)
• 빈도 배열
• 시간복잡도: O(n · k)
• 공간복잡도: O(n)

---

📝 이번 문제에서 얻은 깨달음

• 애너그램 문제의 핵심은 “순서가 아니라 구성” 이다.
• 정렬은 가장 직관적이고 안전한 방법
• 빈도 배열은 성능 최적화 관점에서 좋은 대안

👉 결국 중요한 건
“어떤 기준을 key로 삼을 것인가”를 정확히 정의하는 것이었다.

• computeIfAbsent는 Map + List 문제의 핵심 무기! 암기하자.
• Java에서의 String을 정렬하려면 charArray로 변환이 필요하다! 암기하자.