LeetCode 49. Group Anagrams

49. Group Anagrams

문제

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.

---

주어진 문자열 배열 strs을 아나그램(Anagram) 그룹으로 묶습니다. 답을 어떤 순서로든 반환할 수 있습니다.

아나그램(Anagram)은 다른 단어나 구문의 문자를 재배열하여 일반적으로 원래의 모든 문자를 정확히 한 번 사용하여 형성된 단어나 구문을 의미합니다.

---

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.

나의 해답

• 아쉬운점
  - 문제의 조건을 잘 읽으면 소문자로만 이루어진 문자라고 했는데 정렬을 진행한 점
  - ArrayList의 생성자를 잘 활용하지 못한 점, 아래의 코드를 사용하면 두 번째 반복문은 제거할 수 있었음
  - return new ArrayList(map.values());
• HashTable을 사용해서 문제를 해결하는 것 까지는 좋았다. 여기서의 병목은 문자열을 정렬하는 부분이다. 정렬에 KlogK 의 시간복잡도가 소요되는데 배열을 사용해서 문자열의 count를 만들고 그 배열을 이용해 key를 만드는 것을 생각하지 못했다. 문자열 문제에서 int[] count = new int[26] , count[c - 'a']++ 의 패턴이 자주 등장하는 것 같다. (해답2 참고)

class Solution {

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

		for (String s : strs) {
			String key = s.toLowerCase();
			String sortedKey = sortingString(key);

			List<String> value = map.getOrDefault(sortedKey, new ArrayList<>());
			value.add(s);
			map.put(sortedKey, value);
		}

		List<List<String>> answer = new ArrayList<>();

		for (Map.Entry<String, List<String>> entry : map.entrySet()) {
			List<String> value = entry.getValue();
			answer.add(value);
		}

		return answer;
	}

  
	public String sortingString(String s) {
		char[] charArray = s.toCharArray();
		Arrays.sort(charArray);

		return new String(charArray);
	}
}

해답

1. 정렬된 문자열을 카테고리화

• 이미지 출처 leetcode

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs.length == 0) return new ArrayList();
        
        Map<String, List> ans = new HashMap<String, List>();
        for (String s : strs) {
            char[] ca = s.toCharArray();
            Arrays.sort(ca);
            String key = String.valueOf(ca);
            if (!ans.containsKey(key)) ans.put(key, new ArrayList());
            ans.get(key).add(s);
        }
        return new ArrayList(ans.values());
    }
}

복잡도 분석

• 시간 복잡도
  - N이 strs 배열의 길이이고, K가 각 문자열의 최대 길이라고 정한다. 바깥 반복문이 일단 O(N), 그리고 정렬을 할 때 각 문자의 길이인 K만큼의 시간 복잡도를 소요한다. O(KlogK).
  - 최종 시간복잡도는 O(NKlogK)
• 공간 복잡도
  - O(NK)

2. Categorize by Count

• 이미지 출처 leetcode

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs.length == 0) return new ArrayList();
        
        Map<String, List> ans = new HashMap<String, List>();
        int[] count = new int[26];
        
        for (String s : strs) {
		    // 각 문자마다 새로운 배열을 사용하지 않고, 아래의 코드를 통해 배열을 0으로 초기화 해준다.
            Arrays.fill(count, 0);
            // 각 문자열의 알파벳 개수만큼 count 배열에 기록한다.
            for (char c : s.toCharArray()) count[c - 'a']++;

			// count 배열에서 만든 알파벳 구성 조합으로 식별할 수 있는 하나의 키를 만든다
			// "abc" 였으면
			// "#1#1#1#0#0#0...#0" 의 키가 만들어졌을 것
            StringBuilder sb = new StringBuilder("");
            for (int i = 0; i < 26; i++) {
                sb.append('#');
                sb.append(count[i]);
            }

			// 위에서 만든 키로 map에 해당 문자가 존재하는지 확인한다.
            String key = sb.toString();
            if (!ans.containsKey(key)) ans.put(key, new ArrayList());
            ans.get(key).add(s);
        }
        return new ArrayList(ans.values());
    }
}

복잡도 분석

• 시간 복잡도
  - N이 strs 배열의 길이이고, K가 각 문자열의 최대 길이라고 정한다. 바깥 반복문이 일단 O(N).
  - N만큼의 반복문을 돌면서 K만큼 카운트한다.
  - 키를 만드는 반복문은 상수 시간이 걸리므로 제외한다.
  - 최종 시간복잡도는 O(NK)
• 공간 복잡도
  - O(NK)