Leetcode[day6] - Group Anagrams

Given an array of strings, group anagrams together.

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

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

1. 알고리즘을 해결하기 위해서 생각한 방법

 

 - HashMap 자료구조를 사용한다. 

 - Key는 "eat","tea","ate"를 하나로 묶을 수 있는 sort된 단어가 필요하다.

 - value는 list가 들어간다.

 - key에 대한 value가 있다면, 해당 value인 리스트를 가져와서 sort되지 않은 단어를 추가한다.

 - key에 대한 value가 없다면, List를 새로 생성해준다.

 

2. 알고리즘 작성 중, 어려운 점

 

 - 시간이 오래 걸린 부분은 sortedWord() 메소드를 더 쉽게 구현할 수 없었을까?

 - Map을 만들어서 넣어줄 때, null을 체크해서 로직을 분기해야할까?

 - 알고리즘이 원하는 output을 만들기 위해서 map을 sort하고, 단어에 대한 각 리스트의 길이가 길고, 단어의 spelling이 사전순으로 나와야 한다.

 

3. 내가 작성한 알고리즘

 

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        //푸는 방법 : strs의 단어를 for문으로 출력한다.
        //for문에서 단어를 sort된 상태로 정제한다.
        //sort된 단어는 key, sort되지 않은 단어는 value에 들어간다.
        Map<String,List<String>> map = new HashMap();
        List<List<String>> answer = new ArrayList();
        for(String word : strs){
            String sortedWord = sortedWord(word);
            List<String> answerList = map.get(sortedWord);
            if(answerList == null){
                List<String> tempList = new ArrayList();
                tempList.add(word);
                map.put(sortedWord, tempList);    
            }else{
                answerList.add(word);
                map.put(sortedWord, answerList);
            }
        }
        for(Map.Entry<String, List<String>> mapEntry : map.entrySet()){
            List<String> list = mapEntry.getValue();
            Collections.sort(list);
            answer.add(list);
        }
        answer.sort((o, t1) -> (o.size() - t1.size()));
        return answer;
    }
    
    public String sortedWord(String word){
        String[] splitWords = word.split("");
        Arrays.sort(splitWords);
        String sortedWord = "";
        StringBuilder sb = new StringBuilder();
        for(String oneWord : splitWords){
            sb.append(oneWord);
        }
        return sb.toString();
    }
}

4. 내가 작성한 알고리즘 결과

항상 나는 최하의 효율로 만드는구나^^

 

5. 다른 사람이 작성한 알고리즘 보기

 

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> hash = new HashMap<>();
        for(int i = 0; i < strs.length; i ++)//for 문 : O(n)
        {
            char[] a = strs[i].toCharArray();//String을 풀기 위해서는 toCharArray()
            Arrays.sort(a);//O(nLogn)
            String key = String.valueOf(a);//char[]는 String.valueOf로 형변환 가능 
            if(hash.containsKey(key))//get이 아닌, containsKey를 통해서 쉽게 있는 지 확인
                hash.get(key).add(strs[i]);
            else
            {
                List<String> temp = new ArrayList<String>();//그렇지 않다면 list를 넣어줌
                temp.add(strs[i]);
                hash.put(key, temp);
            }
            
        }
        return new ArrayList<List<String>>(hash.values());
    }
}

 

6. 다른 사람이 작성한 알고리즘을 보고 배운점

 

 - String을 분해하기 위해서는 toCharArray() 메소드를 사용할 것

 - char[] 는 다시 String으로 결합할 때, String.valueOf(new char[])를 통해서 쉽게 결합하라

 - Array.sort는 O(nlogn) 의 복잡도를 갖고 있음

 - HashMap에 아이템이 있는 지 없는 지는 map.get() 보다는 map.contains() 메소드를 활용하라

 

7. 반성할 점

 

 - 전반적으로 비슷한 로직을 생각했다.

 - 하지만, String을 분해하거나 결합하는 디테일이 달랐다. String은 char[]형으로, char[]는 String으로 쉽게 결합할 수 있다는 것을 명심 또 명심

 - Map에 아이템이 있는 지 확인하기 위해서는 null 체크 보다는 contains가 더 말끔하다. 명심 또 명심

 - 디테일한 것을 항상 명심 또 명심 

 

8. 짝짝짝 결과

위에 2.9프로가 더 있다...

문제 : https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/528/week-1/3288/

Account Login - LeetCode