[NeetCode-LeetCode] Group Anagrams JAVA

반응형

728x90

[NeetCode-LeetCode] Group Anagrams - Medium

---

접근

• map

---

풀이

애너그램을 만족하는 문자열끼리 그룹을 만들어 반환하는 문제이다. 애너그램이란 같은 문자로 이루어진 문자열들을 생각하면 된다. eat과 tea는 둘 다 a, e, t로 이루어진 문자열로 애너그램이라고 할 수 있다. 즉 문자열을 구성하는 문자가 같도록 그룹을 지어주면 되는 것이다. 

 

가장 간단하게 생각하면 애너그램이란 같은 문자로 이루어져 있기 때문에 정렬을 할 경우 같은 형태로 변하게 된다. 각 값들을 정렬을 하여 비교하게 되면 쉽게 구할 수 있을 거 같았지만 기본적으로 문자열 전체를 한 번 순회하는데 n 각 문자열을 정렬하는데 문자열 길이만큼 k log k라는 시간이 소요되기 때문에 결국 n * k log k라는 시간이 소요될 것이고 LeetCode에서 문제를 풀 때 이 문제를 O(n)으로 풀어봐라라는 등 더 성능이 좋은 코드들이 많았기에 좀 더 생각을 해봤으나 답이 안 나와 일단 저 방법대로 풀었다.

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

        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String sortedStr = new String(chars);

            if (!map.containsKey(sortedStr)) {
                map.put(sortedStr, new ArrayList<>());
            }
            map.get(sortedStr).add(str);
        }

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

map을 이용해 애너그램을 만족하는 단어들을 리스트에 값으로 보관하여 결과로 반환하는 코드이다. 키로는 정렬된 문자열을 사용하여 처리한다. 

map

대표적인 방법은 맞았던 거 같다. 

---

추상 클래스

추상 클래스를 통해 익명 클래스로 정의를 하는 방법이다. 사실 내부 로직 자체는 거의 동일하고 동적으로 익명 클래스를 구현해 반환하면서 실행 시간을 줄인 부분 정도가 차이가 있다고 보면 될 거 같다. 

    private List<List<String>> ans;

    public List<List<String>> groupAnagrams(String[] strs) {
        return new AbstractList<List<String>>() {
            public List<String> get(int index) {
                if (ans == null) init(); 
                return ans.get(index); 
            }
            public int size() {
                if (ans == null) init(); 
                return ans.size(); 
            }

            public void init() {
                Map<String, List<String>> hm = new HashMap<>();
        
        for (String s : strs) {
            char[] count = new char[26]; 
            for (char c : s.toCharArray()) {
                count[c - 'a']++;
            }
            String key = new String(count); 
            hm.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }

                ans = new ArrayList<>(hm.values());
            }
        };
    }

변환하는 로직 자체는 동일하게 map을 사용하여 구현하게 되는데 정렬을 하는 대신 문자가 등장하는 빈도수를 계산하여 빈도 값을 문자열로 만들어 키로 사용하였다. abc라는 문자열이 있다면 count 배열에는 [1,1,1,0,0,..,0,0] 형태로 저장이 될 것이고 abc라는 문자열의 키 값은 1110000... 000이 되어 사용되게 된다. 같은 애너그램이라면 동일한 빈도수를 가지게 될 것이라 키 값으로 사용하기는 적당하다. 그리고 문자열의 길이가 길어질수록 키 값을 구하는 과정에서 정렬을 통해 구하던 코드와 성능 차이가 발생할 가능성도 있다. 

추상 클래스

 

---

전체 코드

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

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

            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<>());
            }
            map.get(key).add(str);
        }

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

 

추상 클래스

import java.util.AbstractList;
class Solution {
    private List<List<String>> ans;

    public List<List<String>> groupAnagrams(String[] strs) {
        return new AbstractList<List<String>>() {
            public List<String> get(int index) {
                if (ans == null) init(); 
                return ans.get(index); 
            }
            public int size() {
                if (ans == null) init(); 
                return ans.size(); 
            }

            public void init() {
                Map<String, List<String>> hm = new HashMap<>();
        
        for (String s : strs) {
            char[] count = new char[26]; 
            for (char c : s.toCharArray()) {
                count[c - 'a']++;
            }
            String key = new String(count); 
            hm.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }

                ans = new ArrayList<>(hm.values());
            }
        };
    }
}