[자바 알고리즘 인터뷰] 6장 문자열 처리(5) 그룹 애너그램

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

 

 

 

- 문자열 배열을 받아 애너그램 단위로 그룹핑하라 

 

풀이 1) 정렬하여 비교 

 

- 애너그램을 이루는 단어들을 정렬하면 모두 같은 값을 갖게 된다. 

 

- 우선, 정렬한 값을 보관하기 위한 맵을 선언한다. 

- 하나의 키에 애너그램인 여러 개의 값이 추가될 수 있기 때문에 값은 리스트 형태가 되며, 따라서 맵은 리스트를 값으로 둔 형태로 선언한다. 

 

//애너그램 결과를 보관하기 위한 맵 선언
Map<String, List<String>>results = new HashMap<>();

 

- 입력값을 하나씩 순회하며 정렬한다.

//입력값인 문자열 배열을 순회 
for(String s : strs) {
	//문자열을 문자 배열로 변환
     char[] chars = s.toCharArray();
            
     //문자 배열 정렬 
     Arrays.sort(chars);

 

- 정렬된 문자는 chars라는 문자 배열에 정렬된 순서로 나열된다. 

- 이제 이 배열을 맵의 키로 사용하기 위해 다시 문자열로 만들고 처음에 만들었던 results에 이 값을 삽입한다.

 

//문자 배열을 키로 하기 위해 다시 문자열로 변환
 String key = String.valueOf(chars);

//만약 기존에 없던 키라면 빈 리스트를 삽입
if(!results.containsKey(key))
       results.put(key, new ArrayList<>());
//키에 해당하는 리스트에 추가
results.get(key).add(s);
}

 

 

- 이제 Map<String, List<String>>인 결과 변수 results를 문제에서 요구한 출력 형태로 바꿔주면 된다. 

- Map<String,List<String>>을 List<List<String>>으로 바꿔준다. 

 

//문제에서 요구하는 출력값 형태로 변경
return new ArrayList<>(results.values());

 

 

import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        //애너그램 결과를 보관하기 위한 맵 선언
        Map<String, List<String>>results = new HashMap<>();

        //입력값인 문자열 배열을 순회 
        for(String s : strs) {
            //문자열을 문자 배열로 변환
            char[] chars = s.toCharArray();
            
            //문자 배열 정렬 
            Arrays.sort(chars);

            //문자 배열을 키로 하기 위해 다시 문자열로 변환
            String key = String.valueOf(chars);

            //만약 기존에 없던 키라면 빈 리스트를 삽입
            if(!results.containsKey(key))
                results.put(key, new ArrayList<>());
            //키에 해당하는 리스트에 추가
            results.get(key).add(s);
        }

        //문제에서 요구하는 출력값 형태로 변경
        return new ArrayList<>(results.values());

    }
}

 

실행 시간 : 6밀리초