[Leetcode Top Interview 150] 49. Group Anagrams

난이도 : medium

문제링크

• string 배열이 주어진다 : strs
• strs 중, 서로 anagram인 문자열들을 그룹핑하고, 2차원 배열로 리턴하라
• ex) Input: strs = ["eat","tea","tan","ate","nat","bat"]
        Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

 

• anagram은 또 다른 단어의 재구성을 통해원본 단어를똑같이 만들 수 있는 단어를 뜻한다
• 반드시 모든 문자를 한번씩 사용하여 구성해야 한다
  • ex) s = "anagram", t= = "nagaram" => true
  • ex) s = "ab", t= = "a" => false (s의 문자 b를 사용하지 않았음)

 

1. 접근법

• 해시테이블 사용
  • anagram 대표문자 - anagram 배열
    • anagram 대표문자는 anagram을 오름차순한 값
    • 같은 anagram의 오름차순값은 같은 값이므로 이렇게 정함
• strs를 한 문자씩 순회하면서 
  • key에 대한 value가 없다면, key를 담은 새로운 arrayList를 생성해서 put함
  • key에 대한 value가 있다면, value인 arrayList에 key값을 추가해서 put함

 

3. 구현 코드

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {                
        if (strs.length == 0) {
            return List.of(List.of(strs));
        }

        List<List<String>> ans = new ArrayList<>();
        Map<String, List<String>> map = new HashMap<>();

        for (String str : strs) {
            String strKey = ascending(str);
            List<String> strValue;
            
            if (map.containsKey(strKey)) {
                strValue = map.get(strKey);
                strValue.add(str);
            } else {
                strValue = new ArrayList<>();
                strValue.add(str);
                map.put(strKey, strValue);
            }
        }

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

        return ans;
    }

    private String ascending(String key) {        
        char[] keyArr = key.toCharArray();
        Arrays.sort(keyArr);

        StringBuffer newKey = new StringBuffer();
        for (char c : keyArr) {
            newKey.append(c);
        }

        return newKey.toString();
    }
}

 

4. 시간복잡도, 공간복잡도 예상

• 시간복잡도 : O(n*mlogm) - 모든 데이터를 순회하며, 순회할때마다 정렬하는 비용이 발생함
• 공간복잡도 : O(n) - 모든 데이터를 생성해야 함

 

5. 개선점

• 대표 anagram을 정렬로 하지 않고 다른 방법이 없을까?
  • 시간복잡도에서 성능상 손해가 있다

 

6. 회고

• 대표 anagram을 잡는 법이 떠오르지 않아 강의를 들었다

class Solution {
    class AnagramKey {
        public Integer[] visited;

        public AnagramKey(String key) {
            this.visited = new Integer[26];
            fill(key);
        }

        public int hashCode() {
            int result = 17;
            for (int i = 0; i < visited.length; i++) {
                result += 31 * visited[i];
            }

            return result;
        }

        public boolean equals(Object obj) {
            if (obj == this) {
                return true;
            }

            if (obj == null || obj.getClass() != getClass()) {
                return false;
            }

            AnagramKey other = (AnagramKey) obj;
            for (int i = 0; i < visited.length; i++) {
                if (!this.visited[i].equals(other.visited[i])) {
                    return false;
                }
            }

            return true;
        }

        private void fill(String key) {
            Arrays.fill(this.visited, 0);

            for (char c : key.toCharArray()) {
                int idx = c - 'a';
                this.visited[idx] += 1;
            }
        }
    }

    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs.length == 0) {
            return List.of(List.of(strs));
        }

        List<List<String>> ans = new ArrayList<>();
        Map<AnagramKey, List<String>> map = new HashMap<>();

        for (String str : strs) {
            AnagramKey strKey = new AnagramKey(str);
            List<String> strValue;

            if (map.containsKey(strKey)) {
                strValue = map.get(strKey);
                strValue.add(str);
            } else {
                strValue = new ArrayList<>();
                strValue.add(str);
                map.put(strKey, strValue);
            }
        }

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

        return ans;
    }
}

(출처 : NeetCode)

• anagram의 key를 나타내는 AnagramKey라는 클래스를 생성하였다
  • key의 각 문자는 소문자이므로
  • 소문자별 카운트를 가지는 Integer[26] 배열을 필드를 선언하였다
  • AnagramKey 클래스는 HashMap에 들어갈 것이므로 equals()와 hashCode()를 오버라이딩 해준다
    • 동일성 여부는 원소별 카운트가 정확히 일치하는 지 여부와 같다
    • 각 필드의 Integer배열인 visited를 순회하면서 값의 일치여부를 체크한다
• 시간복잡도는 O(n * m)이다