[LeetCode/MEDIUM] 49. Group Anagrams (JAVA) : 문제&풀이

 

 
애너그램(철자 순서를 바꾼 말) 관계의 문자열끼리 묶어 리스트로 반환하는 문제이다.
 
String 배열을 매개변수로 받는 groupAnagrams 메서드의 틀이 주어진다.
 

Problem :

public class GroupAnagrams {
    public List<List<String>> groupAnagrams(String[] strs) {

    }
}

풀이는 groupAnagrams 메서드에 작성하면 된다.
 

Solution :

1. 주어진 문자열 배열로 반복문을 돌며 애너그램 맵에 추가한다.
2. 이 때, 애너그램 맵의 키는 해당 문자열을 정렬한 문자(문자열이 'cat'이라면 키는 ‘act')로 한다.
    1) 애너그램 맵에 동일한 키가 없는 경우, 해당 키로 문자열이 담긴 리스트를 삽입한다.
    2) 애너그램 맵에 이미 동일한 키가 있는 경우, 해당 키의 리스트에 문자열을 추가한다.

public class GroupAnagrams {

	public List<List<String>> groupAnagrams(String[] strs) {

		// 주어진 문자열 배열이 없거나 비어있는 경우
		if(strs == null || strs.length == 0) return new ArrayList<>(new ArrayList<>());

		// 애너그램 관계끼리 담을 맵을 선언
		Map<String, List<String>> anagramMap = new HashMap<>();

		// 문자열 배열로 반복문
		for(String str : strs){
            
			// 문자열을 정렬하여 애너그램 맵의 키 생성
			char[] charArray = str.toCharArray(); // ['c','a',t']
			Arrays.sort(charArray); // ['a','c','t']
			String key = String.valueOf(charArray); // "act"

			// 애너그램 맵에 키가 있으면 해당 값에 추가하고, 없으면 새로 삽입
			if(anagramMap.containsKey(key)){
				anagramMap.get(key).add(str);
			}else{
				anagramMap.put(key, new ArrayList<>(Arrays.asList(str)));
			}
		}

		// 애너그램 맵에서 키위를 제외한 문자열 그룹을 리스트로 반환
		return new ArrayList<>(anagramMap.values());
	}
}

 
 

Sample(Test) :

public class GroupAnagrams {

	public List<List<String>> groupAnagrams(String[] strs) {

		// 주어진 문자열 배열이 없거나 비어있는 경우
		if(strs == null || strs.length == 0) return new ArrayList<>(new ArrayList<>());

		// 애너그램 관계끼리 담을 맵을 선언
		Map<String, List<String>> anagramMap = new HashMap<>();

		// 문자열 배열로 반복문
		for(String str : strs){
            
			// 문자열을 정렬하여 애너그램 맵의 키 생성
			char[] charArray = str.toCharArray(); // ['c','a',t']
			Arrays.sort(charArray); // ['a','c','t']
			String key = String.valueOf(charArray); // "act"

			// 애너그램 맵에 키가 있으면 해당 값에 추가하고, 없으면 새로 삽입
			if(anagramMap.containsKey(key)){
				anagramMap.get(key).add(str);
			}else{
				anagramMap.put(key, new ArrayList<>(Arrays.asList(str)));
			}
		}

		// 애너그램 맵에서 키위를 제외한 문자열 그룹을 리스트로 반환
		return new ArrayList<>(anagramMap.values());
	}

	public static void main(String[] args) {
		String[] strs = {"eat","tea","tan","ate","nat","bat"};

		GroupAnagrams g = new GroupAnagram();
		g.groupAnagrams(strs);
	}
}

 
 
위 테스트 코드의 Input과 Output은 다음과 같다.

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