30-Day LeetCoding Challenge - 6Day (Group Anagrams)

Anagrams이란?

어구전철(語句轉綴) / Anagram
일종의 말장난으로 어떠한 단어의 문자를 재배열하여 다른 뜻을 가지는 다른 단어로 바꾸는 것을 말한다. 고대 유대인들이 히브리어로 하곤 했고, 중세 유럽에도 큰 인기를 끌었다. 프랑스 궁정에서는 '왕을 위해 애너그램을 하는 사람'을 고용하기도 했을 정도다. 중세의 대표적인 어구전철은 라틴어로 된 아베 마리아의 애너그램이다.

애너그램[나무위키]

Group Anagrams

Given an array of strings, group anagrams together.

Example:

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note:

• All inputs will be in lowercase.
• The order of your output does not matter.

Solution

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List> hashStr = new HashMap<String,List>();
	for (String str : strs) {
		char[] arr = str.toCharArray();
		Arrays.sort(arr);
		String key = String.valueOf(arr);
		if (!hashStr.containsKey(key)) {
			hashStr.put(key, new ArrayList());
		}
		hashStr.get(key).add(str);
	}
	return new ArrayList(hashStr.values());
   }
}

1. strs[] 배열에 ["eat", "tea", "tan", "ate", "nat", "bat"] 가 들어온다고 가정하자
2. strs[] 배열에서 첫 번째 인덱스의 문자열부터 char[] 배열에 담은 뒤 정렬한다.
   • 정렬을 하게되면 ["aet","aet","ant","aet","ant","abt"] 이런식으로 앞에서 하나씩 정렬될 것이다.
3. 정렬한 배열을 valueOf()메소드를 이용해 String으로 변환한 뒤 해당 String 객체를 키 값으로 사용할 것 이다.
4. 만약 hashStr객체에 key값으로 key값이 존재하지 않으면 hashMap에 해당 key와 값을 put 한다.
5. for문이 끝나면 새로운 ArrayList를 반환한다.

마침

이번 문제에서 가장 핵심 포인트는 strs[]배열의 값들을 char[] 배열로 변환한 뒤 정렬을 하고 해당 값들을 key값으로 사용했다는 것이다.

요즘 면접 보러 다니느라 하루 이틀 밀리기 시작했다.. 밀려도 꾸준히 해야지