[LeetCode] 49. Group Anagrams - 문자열(String) + 해시맵(HashMap) JAVA

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

코드설명

문자열(String) + 해시맵(HashMap) 를 활용합니다.

 

문제의 아이디어입니다.

1. 각 문자열을 모두 각각 정렬합니다.

2. HashMap에 해당 문자열을 넣습니다. 그리고 OriginalStr(정렬되기 이전의 값)도 List에 함께 넣어줍니다.

3. answerList에 hashmap Value들을 모두 넣습니다.

 

이 문제의 경우 HashMap<String, List<String>>과 같이 Key값에 List<String>을 사용함으로써 문제가 매우 간단해졌습니다. 처음에 이 부분을 떠올리지 못해, 모두 직접 List 형태로 관리하여야 하나, 혹은 처음에 틀린 코드처럼 Node로 관리해서 정렬하여야 하나 생각했습니다.

HashMap을 사용하여 문제가 매우 간단해집니다.

 

또, 구현을 하면서, 여러가지 구현문제를 겪었습니다.

첫번째는 chars[].toString()이 JAva ORacle Docs에 존재하여 바로 사용했지만, 주소값이 나왔습니다. Description을 보니, Object(Reference Type, 배열, Integer, character, Class 와 같은)들이 사용할 수 있는 함수였습니다.

가장 근본적인 이유는, toString()은 Object 클래스에서 상속된 메소드입니다. 그렇기에 chars[]는 Object 타입이기에 그렇습니다. 만약 Char ch 를 ch.toString()으로 작동할경우에는 작동합니다.(하지만 이 경우에는 1개의 문자밖에 변환안되기에 의미가 없습니다. 그 대신에 new String(char[] ch) 를 사용합니다.)

 

두번째는, hashmap.values() 의 반환값은 Collection<V>입니다. 즉, Key값인 List<String>을 다시 Collection<V>로 묶습니다. 그리고  List<List<String>> answer 의 경우 한번에 Collection<V>를 삽입하기 위해 addAll함수를 사용하여야만 합니다.

사실, 이렇게 풀지않고 foreach 구문을 사용해도 됩니다.

 

세번쨰는, 자바의 다이아몬드 연산자가 타입추론을 진행하기에 우변에서 제네릭 타입을 명시하지 않아도 됩니다.

HashMap<String, List<String>> hashmap = new HashMap<>();
// HashMap<String, List<String>> hashmap = new HashMap<String, List<String>>();

코드

정답코드1입니다.

import java.util.*;
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> answer = new ArrayList<>();
        HashMap<String, List<String>> hashmap = new HashMap<>();
        // HashMap<String, List<String>> hashmap = new HashMap<String, List<String>>();

        for(int i=0; i<strs.length; i++){
            char[] chars = strs[i].toCharArray();
            Arrays.sort(chars);
            String sortedStrs = new String(chars);
            // chars.toString error. because char[] is object.
            // String sortedStrs = Arrays.toString(chars);

            if(hashmap.containsKey(sortedStrs)==false){
                hashmap.put(sortedStrs, new ArrayList<String>());
                hashmap.get(sortedStrs).add(strs[i]);
            }else {
                hashmap.get(sortedStrs).add(strs[i]);
            }
        }

        // for(Map.Entry<String, List<String>> entry : hashmap.entrySet()){
        //     answer.add(entry.getValue());
        // }
        answer.addAll(hashmap.values());
        return answer;
    }
}

처음에 작성한 틀린 코드입니다.

import java.util.*;
class Solution {
    //
    public List<List<String>> groupAnagrams(String[] strs) {
        char[][] chars = new char[strs.length][101];
        Node[] node = new Node[strs.length];

        //eat
        //tea
        //tan/
        //ate
        //nat
        //bat 

        //각 단어들을 오름찻누으로 
        //aet
        //aet
        //

        //aet
        //aet
        //aet
        //bat




        for(int i=0; i<strs.length; i++){
            chars[i] = strs[i].toCharArray();
            Arrays.sort(chars[i]);

            StringBuilder sb = new StringBuilder();
            for(int j=0; j<chars[i].length; j++){
                sb.append((chars[i].charAt(j).toString()));
            }
            System.out.print(sb.toString());
            node[i] = new Node(strs[i], chars[i].toString());
        }

        Arrays.sort(node);
        for(Node v : node){
            System.out.println(v.original+ "??"+ v.sorted);
        }
        
        return null;

    }

    class Node implements Comparable<Node>{
        String original;
        String sorted;

        @Override
        public int compareTo(Node other){
            return this.sorted.compareTo(other.sorted);
        }

        public Node(String original, String sorted){
            this.original = original;
            this.sorted = sorted;
        }
    }
}