백준 6566 애너그램 그룹 java

HashMap<String, HashSet<String>> 을 만들어서 Key = 정렬된 문자열, value는 모든 문자열을 넣는다.
이때, HashSet으로 넣기 때문에 정렬이 사라짐으로, HashMap<String, Integer>를 만들어 각 그룹의 사이즈를 따로 센다.

(2) 정렬

각 그룹 내부 구성원을 사전 순으로 정렬한다.
그룹끼리의 우선순위도 정한다. -> 위에서 구한 그룹 사이즈 크기가 큰 순, 같다면 사전 순으로 그룹 내 가장 앞에 있는 단어끼리의 사전 순

(3) 출력

문제의 요구사항에 맞게 출력한다.

(4) 시간복잡도 분석 ⏳

입력은 30,000개 인데, 각 단어의 크기가 얼마인지는 나와있지 않다.
맨 첫 작업인 입력이 시간 복잡도가 가장 많이 걸릴 것이다. 문자열의 개수를 N, 문자열의 평균 길이를 L이라고 할 때, O(N * L * logL) 이 빅오이다.
(N개 순회 -> HashMap에 넣기 (정렬 후 삽입 -> L log L)

3. 코드 🌐


import java.util.*;
    import java.io.*;
import java.util.Map.Entry;
import java.util.function.Supplier;

// b 6566 애너그램 그룹
public class Main {
    static HashMap<String, Integer> cnt = new HashMap<>();
    static HashMap<String, HashSet<String>> map = new HashMap<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true){
            String row = br.readLine();
            if(row == null || row.isBlank()) break;
            String convert = sort(row);
            map.compute(convert, (k,ov) -> (ov == null? new HashSet<>() : ov)).add(row);
            cnt.compute(convert, (k, ov) -> (ov == null? 1: ov+1));
        }        ArrayList<ArrayList<String>> group = new ArrayList<>();
        for(Entry<String, HashSet<String>> word_list : map.entrySet()){
            ArrayList<String> words = new ArrayList<>();
            for(String word : word_list.getValue()) words.add(word);
            Collections.sort(words);
            group.add(words);
        }        group.sort((a,b) -> {
            String convertA = sort(a.get(0));
            String convertB = sort(b.get(0));
            int sizeA = cnt.get(convertA);
            int sizeB = cnt.get(convertB);
            if(sizeA == sizeB) return a.get(0).compareTo(b.get(0));
            return sizeB - sizeA;
        });
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < Math.min(5, group.size()); i++){
            String key = sort(group.get(i).get(0));
            sb.append("Group of size ").append(cnt.get(key)).append(": ");
            for(String word : group.get(i)){
                sb.append(word).append(" ");
            }            sb.append(".").append("\\n");
        }        System.out.printf("%s", sb.toString());
    }
    public static String sort(String origin){
        char [] temp = origin.toCharArray();
        Arrays.sort(temp);
        return String.valueOf(temp);
    }
}