.leetcode(49. Group Anagrams)

문제

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

문제 풀기 전

1. 알파벳을 하나씩 지워가볼까 생각했는데 하다가 도저히 복잡해져서 안되겠다.
2. 문자를 정렬을 통해 같게 만들어서 map으로 관리하면 되겠다.

직접 푼 풀이

소요시간: 21분(22:00 ~ 22:21)

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        int n = strs.length;
        Map<String, List<String>> map = new HashMap<>();
        for (int i=0; i<n; i++) {
            String target = strs[i];
            char[] strArray = target.toCharArray();
            Arrays.sort(strArray);
            String sortedStr = String.valueOf(strArray);

            if (map.containsKey(sortedStr)) {
                List<String> list = map.get(sortedStr);
                list.add(target);
                map.put(sortedStr, list);
            } else {
                List<String> list = new ArrayList<>();
                list.add(target);
                map.put(sortedStr, list);
            }
        }

        return map.values().stream().collect(Collectors.toList());
    }
}

느낀점

1. 왠지 한글자씩 빼는 방식도 될거같은데 결국 그렇게 풀진 못했다.
2. map과 Arrays.sort를 쓰면서 이렇게 해도 되는건가 싶었는데 풀이도 이렇게 풀었다. 치트키 같아도 역시 풀리는대로 우선 풀어야겠다. charArray를 다시 String으로 만들어주는데 String.valueOf가 좋다.
3. 다른방식으로는 map을 여전히 이용하되 키값을 정렬이 아닌 숫자카운팅으로 하는 방식이다. 아래와 같이 풀수 있다.
4. 숫자를 세서 키를 만드는 방식이 아주 새로웠다.

솔루션 공부 후 추가로 푼 풀이

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        int n = strs.length;
        Map<String, List<String>> map = new HashMap<>();
        for (int i=0; i<n; i++) {
            String target = strs[i];
            String key = makeCountKey(target);

            if (map.containsKey(key)) {
                List<String> list = map.get(key);
                list.add(target);
                map.put(key, list);
            } else {
                List<String> list = new ArrayList<>();
                list.add(target);
                map.put(key, list);
            }
        }

        return map.values().stream().collect(Collectors.toList());
    }

    private String makeCountKey(String target) {
        int[] alphabets = new int[26];
        for(int i=0; i<target.length(); i++) {
           alphabets[(int)(target.charAt(i)-'a')]++; 
        }

        StringBuilder builder = new StringBuilder();
        for (int i=0; i<26; i++) {
            builder.append(alphabets[i]).append(",");
        }

        return builder.toString();
    }
}

누적되는 알고리즘 접근 설명서

2021/01/09 - [알고리즘 풀이] - .leetcode(알고리즘 문제풀이 접근)