[Baekjoon] 6566_애너그램 그룹

문제(출처: https://www.acmicpc.net/problem/6566)

---

< 애너그램 그룹 >

 

문제 풀이 

 

만약 다음과 같이 입력이 들어온다면

caret
carte
cater

 

HashMap에 key 값으로 "acert"을, value로 [caret, carte, cater]를 저장하는 방식으로 애너그램 그룹을 구한다.

* 만약 "abc"라는 문자열이 4개 들어온다면 그룹 크기는 4이고 출력은 "abc" 한 번만 출력해야 한다.

 

my solution (Java)

 import java.io.BufferedReader;
 import java.io.BufferedWriter;
 import java.io.IOException;
 import java.io.InputStreamReader;
 import java.io.OutputStreamWriter;
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collections;
 import java.util.Comparator;
 import java.util.HashMap;
 import java.util.HashSet;
 
 public class _6566_ { // 애너그램 그룹
 
 	public static void main(String[] args) throws IOException {
 		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
 		String str = "";
 
 		HashMap<String, ArrayList<String>> map = new HashMap<>();
 
 		while ((str = bf.readLine()) != null) {
 			char[] arr = str.toCharArray();
 
 			Arrays.sort(arr);
 
 			String key = new String(arr);
 			if (map.containsKey(key)) {
 				map.get(key).add(str);
 			} else {
 				ArrayList<String> set = new ArrayList<>();
 				set.add(str);
 
 				map.put(key, set);
 			}
 		}
 
 		for (String key : map.keySet()) {
 			Collections.sort(map.get(key));
 		}
 
 		ArrayList<String> list = new ArrayList<>(map.keySet());
 		Collections.sort(list, new Comparator<String>() {
 			@Override
 			public int compare(String o1, String o2) {
 				if (map.get(o2).size() == map.get(o1).size()) {
 					return map.get(o1).get(0).compareTo(map.get(o2).get(0));
 				}
 				return map.get(o2).size() - map.get(o1).size();
 			}
 		});
 
 		for (int i = 0; i < Math.min(5, list.size()); i++) {
 
 			bw.write("Group of size " + map.get(list.get(i)).size() + ": ");
 
 			HashSet<String> set = new HashSet<>();
 			for (int j = 0; j < map.get(list.get(i)).size(); j++) {
 				set.add(map.get(list.get(i)).get(j));
 			}
 
 			ArrayList<String> result = new ArrayList<>(set);
 			Collections.sort(result);
 
 			for (int j = 0; j < result.size(); j++) {
 				bw.write(result.get(j) + " ");
 			}
 			bw.write(".\n");
 		}
 		bw.flush();
 	}
 }

변수)
str : 단어
map : HashMap <정렬된 단어, ArrayList <>>
arr : 단어 -> char 배열
key : 정렬된 단어
list : HashMap key -> ArrayList

 

입력이 없을 때까지 단어를 입력받아 다음 과정을 거친다.

1) 입력받은 단어를 char 배열로 변환

2) char 배열 정렬

3) char 배열을 String으로 변환 후 HashMap에 key 값으로 있다면 value에 입력받은 단어를 추가, key 값에 없다면 key 값으로 정렬된 단어를, value로 ArrayList를 저장한다.

 

HashMap의 value 값을 정렬한다. HashMap의 key 값을 ArrayList로 변환 후 다음 기준에 맞춰 정렬한다.

1) HashMap의 value 크기를 기준으로 내림차순 정렬

2) value 크기가 같다면 각 그룹에서 가장 사전 순으로 앞서는 단어의 사전 순으로 정렬

 

크기가 가장 큰 애너그램 다섯 개를 출력한다. 만약, 그룹의 수가 다섯 개보다 작다면 모두 출력한다. 이때, 같은 단어를 한 번만 출력해야 하기 때문에 HashSet을 사용하여 중복 처리한 후 정렬하여 출력한다.

---

---