LeetCode: 49번 (Group Anagrams) [JAVA]

문제 링크

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

Group Anagrams - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 주어진 String 문자열에 대한 정보를 가지는 AlphabetInWord 클래스 생성. 해당 클래스의 필드는 알파벳 26문자 길이만큼의 배열로, 생성자로 문자열이 들어올 때 해당 문자열 속 문자들의 개수를 카운트해 배열에 저장
2. 추가로 해당 클래스의 hashCode(), equals() 함수를 오버라이딩
3. HashMap<AlphabetInWord, List<String>> 해시 맵 생성
4. 전체 strs 배열을 돌며 해당 문자열을 바탕으로 AlphabetInWord 클래스를 생성 후, 해당 키값을 바탕으로 기존 해시맵에 키가 존재한다면 값에 있는 리스트에 해당 문자열을 추가, 없다면 새로운 List를 생성 후 값 부분에 추가
5. 이후 HashMap을 다시 한 번 이터레이터를 통해 돌며 값 부분의 List를 정답 List<List<String>>에 추가 후 반환

 문제에서 요구하는 부분은 anagram들의 집합을 반환하는 문제로, 여기서 anagram이란 특정 문자열 속 알파벳들을 한 번씩만 사용해 재정렬하여 만든 문자열을 의미한다. 이 문제를 해결하기 위해 문자열 간의 유사성을 파악하는 방식을 적용할 수도 있지만, 보다 자바스러운 풀이로 문제를 해결했다.
 자바에서 사용되는 HashMap의 경우 키 값에 객체가 올 수 있고, 해당 객체의 hashCode()와 equals()를 재정의하면 충분한 해시맵의 키 값으로 활용할 수 있다. 이에 문제에서 요구하는 anagram의 특징을 나타내는 클래스를 만들고, 해당 클래스의 hashCode()와 equals()를 재정의하면 HashMap에 단순히 문자열들을 넣는 것만으로 anagram의 집합을 쉽게 만들어낼 수 있다.
 우선 특징을 나타내는 클래스 AlphabetInWord를 선언하고, 필드의 경우 알파벳 종류 26개를 길이로 갖는 int 배열을 선언한다. 생성자로는 특정 String 문자열을 받아, 문자열 속 존재하는 알파벳의 개수를 세어 배열에 추가하는 생성자를 생성한다. 이후 hashCode()와 equals() 함수를 재정의하면, HashMap의 키 값으로 활용할 클래스가 완성된다.
 이후 풀이 과정은 단순하다. HashMap<AlphabetInWord, List<String>> 자료구조를 하나 선언한 후, 주어진 strs 배열을 돌며 특정 문자열을 바탕으로 AlphabetInWord를 생성하고, 해시맵에 해당 키값이 존재한다면 값 부분의 리스트에 문자열을 추가하거나 키값이 없다면 새로운 리스트를 하나 만들어 HashMap에 추가하면 된다. 전체 반복을 완료하면, HashMap에 대한 이터레이터를 통해 값 부분의 리스트를 가져와 답으로 반환할 List<List<String>>에 추가한 다음, 이를 반환하면 된다.

 

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> answer = new ArrayList<>();
        HashMap<AlphabetInWord, List<String>> hashMap = new HashMap<>();

        for (int i = 0; i < strs.length; i++) {
            AlphabetInWord alphabetInWord = new AlphabetInWord(strs[i]);

            if (hashMap.containsKey(alphabetInWord)) {//동일한 키가 존재하면 단순 해당 리스트에 추가
                hashMap.get(alphabetInWord).add(strs[i]);
            } else {//존재하지 않으면 새로 리스트를 생성해 추가
                List<String> temp = new ArrayList<>();
                temp.add(strs[i]);
                hashMap.put(alphabetInWord, temp);
            }
        }

        for (Map.Entry<AlphabetInWord, List<String>> entry : hashMap.entrySet()) {//answer에 옮겨담기
            answer.add(entry.getValue());
        }

        return answer;
    }

    class AlphabetInWord{
        int[] alphabets = new int[26];

        public AlphabetInWord(String str) {//주어진 String 기반 생성자
            for (int i = 0; i < str.length(); i++) {
                ++alphabets[str.charAt(i) - 'a'];
            }
        }

        @Override
        public int hashCode() {//해당 클래스 hashCode() 오버라이딩
            int h = 0;

            for (int i = 0; i < alphabets.length; i++) {
                h = 31 * h + alphabets[i];
            }

            return h;
        }

        @Override
        public boolean equals(Object obj) {//해당 클래스 equals() 오버라이딩
            if (obj instanceof AlphabetInWord) {
                return Arrays.equals(this.alphabets, ((AlphabetInWord) obj).alphabets);
            }
            return false;
        }
    }
}

결과