[Leetcode] 49번 - 그룹 애나그램(Anagrams)

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

 

1. 문제 파악

 

애나그램(Anagram): 동일한 문자의 조합으로 이루어진 문자열이면 동일한 값으로 치부

• 문제를 나눠서 정의: 주어진 문자열 배열에서 애나그램인 문자열 끼리 리스트로 묶어서 반환해라.
  1. 문자열끼리 애나그램 판별
  2. 애나그램인 문자열끼리 리스트에 추가
• 시간복잡도 파악:
  1. 1 <= strs.length <= 10000 -> 문자열 배열의 길이: 10000 -> O(nlogn)
  2. 0 <= strs[i].length <= 100 -> 문자열의 길이: 100 -> O(n)
  3. 시간 복잡도 총합: O(n x nlogn)

 

2. 핵심 문제 풀이 도출

 

문제를 나눈것에 대해 풀이를 도출해본다.

1. 애나그램 판별은 어떻게 할까? -> 문자열에서 문자의 개수가 동일한지 확인 -> 너무 복잡 -> 정렬을 하면 동일 문자열인지 판별 가능 -> 단순
2. 정렬한 문자로 애나그램인지 확인했다면 동일한 리스트에 원본 문자열을 추가
3. 애나그램별로 묶은 리스트를 최단시간에 가져와서 요소를 추가하기위하여, HashMap에 정렬한 문자열을 key로 하여금 List<String>에 원본 문자열을 value로 저장한다.

• 문자열 정렬: O(nlogn)
• 문자열 배열 탐색: O(n)

위의 핵심 알고리즘은 문자열 배열을 순차적으로 조회하면서 문자열 정렬을 수행하므로 총 시간 복잡도: O(n x nlogn)에 풀수있다.

 

3. 입출력 케이스 도출

 

주의할점: 메서드의 반환 타입이 List<List<String>>이며, 리스트의 요소에 대한 출력 순서는 무작위여도 된다.

• 일반 케이스:
  • ["eat","tea","tan","ate","nat","bat"] -> [["bat"],["nat","tan"],["ate","eat","tea"]]
  • ["a"] -> [["a"]]
• 엣지 케이스:
  • [""] -> [[""]]

 

4. 핵심 문제 풀이가 케이스에 알맞게 입출력 될수 있는지 대략적으로 확인

1. 입력된 문자열 배열을 순차적으로 조회
2. 문자열을 정렬
3. 정렬된 문자열로 HashMap에 저장된 key가 있는지 확인
4. 정렬된 key가 없다면 ArrayList<String> 타입의 인스턴스를 저장
5. HashMap의 value인 ArrayList<String>를 가져와서 입력된 원본 문자열을 리스트에 저장

 

5. 어떤 자료구조와 알고리즘을 사용할지?

 

자료구조는 기존의 문자 배열인 문자열을 그대로 사용해서 탐색하면 되고, 알고리즘은 사실상 핵심 문제 풀이와 같다.

 

6. 코드로 문제 풀이 구현

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String s: strs) { // O(n)
            char[] arr = s.toCharArray(); 
            Arrays.sort(arr); // 정렬 -> 평균 O(nlogn),  최악 O(n^2) -> 최적화 되어 있어서 O(nlogn)라고 보면된다.
            String key = String.valueOf(arr); // char[] 배열을 String으로 변환
            if (!map.containsKey(key)) { // 중복되는 키가 존재하는지 확인: O(n)
                map.put(key, new ArrayList<>()); // hashmap에 저장할 List 인스턴스 저장: O(n)
            }
            map.get(key).add(s); // 동일한 anagram인 문자열을 List에 추가: O(n)
        }
        return new ArrayList<>(map.values());
    }
}