Group Anagram - 리트코드

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

풀이 과정은 상관없고 정답 코드를 보고 싶으신 분은 세 번째 풀이를 봐주세요!

평가

결과 : 성공
풀이시간 : 21분

시간복잡도를 향상시키기 위해 50분 정도 더 문제를 풀었고 성공했습니다 :)

첫 번째 풀이

아이디어

각각의 str을 Node로 만듭니다.
Node는 원래 문자열과 26 크기의 int 배열 values를 가집니다.
values에는 각 문자가 몇 번 나왔는지 저장합니다.
ex. a -> 0, b -> 1, c -> 2, ... , y -> 24, z -> 25

예를 들어 abbc 라는 문자열의values는 [1,2,1,0,0,.....,0] 이 됩니다.

이후 두 문자가 Anagram인지 확인하기 위해
0부터 25까지 두 문자의 values를 비교합니다.
n1.values[i] != n2.values[i] 라면 해당 문자의 개수가 다르다는 의미이기 때문에 Anagram이 될 수 없습니다.

코드

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        boolean[] checks = new boolean[strs.length];
        List<Node> nodes = new ArrayList<>();
        for(String str: strs) {
            nodes.add(new Node(str));
        }

        int idx = 0;
        List<List<String>> answers = new ArrayList<>();
        for(Node node: nodes) {
            // 이미 애너그램 체크가 됐다면 넘어간다
            if (checks[idx++]) {
                continue;
            }

            // node랑 values가 똑같은 애들을 다 찾는다
            List<String> answer = new ArrayList<>();
            checks[idx - 1] = true;
            answer.add(node.original);

            for(int i=idx; i<nodes.size(); i++) {
                if (checks[i]) {
                    continue;
                }
                // 만약 node와 values가 일치한다면 애너그램이다
                if (isAnagram(node, nodes.get(i))) {
                    checks[i] = true;
                    answer.add(nodes.get(i).original);
                }
            }
            answers.add(answer);
        }

        return answers;
    }

    boolean isAnagram(Node n1, Node n2) {
        for(int i=0; i<26; i++) {
            if (n1.values[i] != n2.values[i]) {
                return false;
            }
        }
        return true;
    }

    static class Node {
        int[] values;
        String original;

        public Node(String original) {
            this.values = new int[26];
            this.original = original;
            for(char each: original.toCharArray()) {
                values[(int) (each - 'a')] += 1;
            }
        }
    }
}

정답이 나오긴 했는데, 시간복잡도가 좋지 않습니다.
560ms로 하위 5퍼센트가 떠서 이대로 넘어가기에는 마음이 불편합니다.
다른 방식의 풀이를 생각합니다.

두 번째 풀이

아이디어

첫 번째 풀이는 for문을 돌며 26개 알파벳이 몇 개씩 나오는지 비교하고 있습니다.
대부분의 문자열은 26개 문자가 다 나오지 않을 겁니다. 예시를 봐도 3개 문자 정도로만 구성되어 있습니다.

만약 xyz와 yyz를 비교한다면 a부터 v까지 22개 문자를 비교해야 합니다.
해당 과정이 비효율적이라고 생각이 들었고, 나온 문자들로만 비교하는 게 좋겠다는 생각을 했습니다.

Node 안에 int[26] 을 가지고 있었다면, char[] sorted를 사용해 나온 문자만 저장합니다.
그리고 문자를 정렬해줍니다.
즉, sorted는 cba -> [a,b,c], abaa -> [a,a,a,b] 이런 식으로 값을 저장합니다.

코드

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        boolean[] checks = new boolean[strs.length];
        List<Node> nodes = new ArrayList<>(strs.length);
        for(String str: strs) {
            nodes.add(new Node(str));
        }

        int idx = 0;
        List<List<String>> answers = new ArrayList<>();
        for(Node node: nodes) {
            // 이미 애너그램 체크가 됐다면 넘어간다
            if (checks[idx++]) {
                continue;
            }

            // node랑 values가 똑같은 애들을 다 찾는다
            List<String> answer = new ArrayList<>();
            checks[idx - 1] = true;
            answer.add(node.original);

            for(int i=idx; i<nodes.size(); i++) {
                if (checks[i]) {
                    continue;
                }
                // 만약 node와 values가 일치한다면 애너그램이다
                if (isAnagram(node, nodes.get(i))) {
                    checks[i] = true;
                    answer.add(nodes.get(i).original);
                }
            }
            answers.add(answer);
        }

        return answers;
    }

    boolean isAnagram(Node n1, Node n2) {
        if (n1.sorted.length != n2.sorted.length) {
            return false;
        }
        for(int i = 0; i< n1.sorted.length; i++) {
            if (n1.sorted[i] != n2.sorted[i]) {
                return false;
            }
        }
        return true;
    }

    static class Node {
        String original;
        char[] sorted;

        public Node(String original) {
            this.original = original;
            this.sorted = original.toCharArray();
            Arrays.sort(this.sorted);
        }
    }
}

560ms -> 280ms 로 조금 더 빨라졌지만, 여전히 퍼센티지가 낮습니다.
이 방법보다 더 효율적인 방법을 찾아야 합니다.

세 번째 풀이

아이디어

근본적인 해결이 필요하다 느꼈습니다.
지금까지의 방식은 두 문자열을 비교할 때마다 문자열의 개수만큼 비교해야 합니다.
해당 방식을 Hash 방식으로 바꿔야 한다는 생각이 들었습니다.

Hash의 키 값을 어떻게 만들 수 있을까 고민하다가, 두 번째 풀이의 char[] sorted 를 String으로 바꾸자는 아이디어가 떠올랐습니다.

두 문자열이 애너그램이라는 이야기는 결국 문자열을 정렬하면 똑같은 값이 나온다는 이야기가 됩니다.
ex. abcc, cabc, ccba 는 모두 정렬하면 abcc가 됩니다

즉, 정렬된 문자열이 같으면 해당 문자열들은 애너그램이다 라는 정의가 나옵니다.
Hash의 Value에 List를 넣고, 정렬한 문자열을 Key로 문자열들을 넣어주는 방식으로 문제를 해결했습니다.

코드

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        boolean[] checks = new boolean[strs.length];
        List<Node> nodes = new ArrayList<>(strs.length);
        for(String str: strs) {
            nodes.add(new Node(str));
        }

        Map<String, List<String>> hash = new HashMap<>();
        for(Node node: nodes) {
            if (!hash.containsKey(node.sorted)) {
                hash.put(node.sorted, new ArrayList<>());
            }
            hash.get(node.sorted).add(node.original);
        }

        List<List<String>> answers = new ArrayList<>();
        for(List<String> value: hash.values()) {
            answers.add(value);
        }
        return answers;
    }

    boolean isAnagram(Node n1, Node n2) {
        return true;
    }

    static class Node {
        String original;
        String sorted;

        public Node(String original) {
            this.original = original;
            char[] sortedTemp = original.toCharArray();
            Arrays.sort(sortedTemp);
            sorted = String.valueOf(sortedTemp);
        }
    }
}