[LeetCode] Java - Group Anagrams

 

6일차 Group Anagrams 입니다.

 

- 문제 

- 풀이

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, Integer> map = new HashMap<>();
        List<List<String>> items = new ArrayList();
        int k = 0;
        for(int i=0; i<strs.length; i++){
            // key 생성하기.
            char[] strChars = strs[i].toCharArray();
            Arrays.sort(strChars);
            String key = new String(strChars);

            if(map.get(key) != null){
                int n = map.get(key);
                List<String> item = items.get(n);
                item.add(strs[i]);
                items.set(n, item);
            }else{
                map.put(key, k++);
                ArrayList<String> item = new ArrayList<>();
                item.add(strs[i]);
                items.add(item);
            }
        }
        return items;

    }    
}

 

같은 알파벳으로 구성된 단어끼리 묶어 출력하는 문제입니다.

처음에는 각각의 문자를 바이트로 변환해서 모두 더한다음 값이 같으면 같은 그룹으로 묶는 방식으로 생각했었습니다.

잘못된 생각이였죠. 시간복잡도도 상당히 높아집니다.

 

그래서 각각의 문자열을 한번의 조회로 구분할 수 있도록 생각해야했습니다.

그래서 위와 같이 HashMap에 그룹을 번호를 저장하고 List에 업데이트는 방식으로 했습니다.

같은 문자인지 확인하는 것은 해당 문자열을 Char의 배열로 변환해서 sort 하고 비교하는 방식을 사용했습니다.

 

Anagrams이라는 문제를 해결할때 해당 방법을 사용하기 때문이죠.

 

이렇게 문제를 해결!