[LeetCode] 49. Group Anagrams - Java

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

Group Anagrams - LeetCode

---

문제

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

Example 3:

Input: strs = ["a"]
Output: [["a"]]

 

Constraints:

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters.

---

풀이

풀이 과정

알파벳 소문자로 이루어진 문자열들의 배열 strs가 주어질 때 각 단어들이 anagram이 되는 단어끼리 묶어서 리스트로 반환하는 문제이다. 

anagram이란 서로 다른 두 문자열의 문자 배치를 바꾸었을 때 같은 문자가 되는 문자열을 의미한다.

알파벳의 길이만큼의 배열을 하나 선언한뒤 각 문자마다 사용된 알파벳의 개수를 카운트하여 해당 결과를 해시값으로 사용한다.
같은 해시값을 가진 문자끼리 묶어서 정답리스트에 추가하도록한다.

우선 최종 반환할 결과 리스트와 각 해시그룹별 문자열 리스트를 저장할 map을 선언한다.

// 최종 결과 리스트
List<List<String>> result = new ArrayList<>();

// 각 anagram 그룹별 문자열을 저장할 map
Map<String, List<String>> map = new HashMap<>();

 

주어진 strs배열의 문자열을 하나씩 탐색한다.
각 문자열에서 사용된 알파벳 개수를 저장할 길이 26만큼의 정수배열을 하나 선언하고 현재 탐색중인 단어의 각 알파벳의 개수를 증가시킨다.
알파벳 배열을 그대로 문자열로 변환하여 그룹키로 사용하고 map의 해당 key의 리스트에 현재 문자열을 추가한다.

// 문자열 하나씩 탐색
for(String word : strs) {
    // 문자열에서 사용된 알파벳 개수를 저장할 정수 배열
    int[] alphabet = new int[26];
    // 현재 탐색문자의 각 알파벳 탐색
    for(char c : word.toCharArray()) {
        // 해당하는 알파벳의 값을 증가
        alphabet[c - 'a']++;
    }
    // 알파벳 map을 문자열로 변환하여 그룹키로 사용
    String groupKey = Arrays.toString(alphabet);

    // map에 그룹키가 존재하지 않는다면 키를 추가
    if(!map.containsKey(groupKey)) {
        map.put(groupKey, new ArrayList<>());
    }

    // 해당 그룹키에 현재 문자열 추가
    map.get(groupKey).add(word);
}

 

map에 담긴 값들을 정답 리스트에 모두 추가하여 최종 return한다.

// map의 값들을 정답 리스트에 추가
for(String key : map.keySet()) {
    result.add(map.get(key));
}

// 결과 리스트 return
return result;

---

 

최종 코드

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 최종 결과 리스트
        List<List<String>> result = new ArrayList<>();
        
        // 각 anagram 그룹별 문자열을 저장할 map
        Map<String, List<String>> map = new HashMap<>();
        // 문자열 하나씩 탐색
        for(String word : strs) {
            // 문자열에서 사용된 알파벳 개수를 저장할 정수 배열
            int[] alphabet = new int[26];
            // 현재 탐색문자의 각 알파벳 탐색
            for(char c : word.toCharArray()) {
                // 해당하는 알파벳의 값을 증가
                alphabet[c - 'a']++;
            }
            // 알파벳 map을 문자열로 변환하여 그룹키로 사용
            String groupKey = Arrays.toString(alphabet);
            
            // map에 그룹키가 존재하지 않는다면 키를 추가
            if(!map.containsKey(groupKey)) {
                map.put(groupKey, new ArrayList<>());
            }
            
            // 해당 그룹키에 현재 문자열 추가
            map.get(groupKey).add(word);
        }
        
        // map의 값들을 정답 리스트에 추가
        for(String key : map.keySet()) {
            result.add(map.get(key));
        }

        // 결과 리스트 return
        return result;
    }
}

---