[leetcode - 49. Group Anagrams] java

문제 설명

1. 문자열의 배열이 주어진다.

2. 아나그램(문자를 섞어서 같은 것들)을 묶으면 됨

3. 순서는 상관 없음

풀이 과정(느린풀이)

1. 처음에는 간단하게 이중 map으로 구했다.

2. 빈도수를 가진 map 을 만들고, 그 map을 다시 key로 가지면서 value 에 String 들을 List로

3. 딱봐도 느릴것같았는데 최저속도로 통과했다ㅋㅋ

코드

class Solution {
    public int[][] merge(int[][] intervals) {
        // 정렬에 대한 얘기가 처음에 없음. 근데 시작점만 정렬해주면 될듯?
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        
        // 최초 배열 만들기용 숫자 적용
        int start = intervals[0][0];
        int end = intervals[0][1];

        List<int[]> arr = new ArrayList<>();

        for(int i=1; i<intervals.length; i++) {
            if(end >= intervals[i][0]) { // 겹칠 수 있다면
                end = Math.max(end, intervals[i][1]); // 겹치고, 뒤에 크기는 더 큰걸로 해야함(앞이 더 클수도 있으니)
            } else {
                int[] ii = {start, end}; // 안겹치면 앞에꺼 더하고
                arr.add(ii);

                start = intervals[i][0]; // 다시 배열 생성용 숫자 적용
                end = intervals[i][1];
            }
        }

        // 끝까지 해서 나왔으면 마지막꺼 적용하기
        int[] ii = {start, end};
        arr.add(ii);

        return arr.toArray(new int[arr.size()][]);    
    }
}

풀이 과정(빠른풀이)

1. 생각을 해 보니, 이거... 어차피 어떤 방식으로든 된다면 그냥 배열로 만들어서 정려하면 되지 않나 싶었다.

2. 그래서 char Array 로 만들고 이를 정렬한 뒤 이를 통해 값 저장

3. 훨씬 빨라짐

코드

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

        for(String str : strs) {
            // 배열로 만들어 sort 하면 아나그램을 하나의 단어로 압축 가능
            char[] chr = str.toCharArray();
            Arrays.sort(chr);
            String sortedWord = new String(chr);

            // 이를 통해 아나그램 key 와 동일한 결과를 내는 모든 String 저장
            List<String> list = hm.getOrDefault(sortedWord, new ArrayList<>());
            list.add(str);
            hm.put(sortedWord, list);
        }

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