[백준] S4 16499번 동일한 단어 그룹화하기 (JAVA)

문제 출처 - Baekjoon

문제는 여기

16499번: 동일한 단어 그룹화하기

[문제] 

소문자로 이루어진 단어 N개가 주어졌을 때, 단어가 총 최소 몇 개의 그룹으로 이루어져 있는지 구하는 프로그램을 작성하시오.

그룹에 속한 단어는 모두 같은 알파벳으로 이루어져 있어야 하고, 개수도 같아야 한다. 즉, 단어를 구성하는 알파벳의 순서만 달라야 한다.

[입력]

첫째 줄에 단어의 개수 N이 주어진다. (2 ≤ N ≤ 100) 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 소문자로만 이루어져 있고, 길이는 10을 넘지 않는다.

[출력]

첫째 줄에 그룹의 최소 개수를 출력한다.

 

 

---

[풀이]

1. 단어를 입력받아 준다.

2. 입력받은 단어를 char 단위로 잘라 char형 배열에 담아준다.

3. 배열에 담긴 값을 정렬한다

4. 정렬된 char형 배열을 다시 String형으로 만들어준다.

5. 해당 단어를 해쉬 셋에 담아준다.

6. 마지막에 해쉬 셋의 크기를 출력한다.

[접근]

1. 단어가 똑같은 문자로 구성이 되어있는지를 판단해야 한다.

2. char단위로 값을 쪼개서 값을 비교해서 같은 단어인지 체크를 하는 것은 시간적으로 너무 오래 걸린다.

3. 해쉬 셋은 값이 중복되지 않기 때문에 쪼개서 특정 순서로 정렬한 것을 넣어주면 중복 처리를 자동으로 할 수 있다.

ex) cat => act / act = > act / tac => act 이렇게 알파벳 순서로 정렬

4. 해쉬 셋에서 자동으로 중복처리가 되었으니 해쉬 셋의 크기를 출력하면 그룹의 개수가 나온다.

[코드]

package BOJ_silver;

import java.io.*;
import java.util.*;

public class Main_S4_16499_김재욱 {
	static int n;
	static char[] word;
	static HashSet<String> set;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		
		set = new HashSet<>(); // 만들어진 단어를 담아줄 해쉬셋
		
		for (int i = 0; i < n; i++) {
			String str = br.readLine(); // 단어 입력받기
			word = str.toCharArray(); // 단어를 char단위로 잘라서 배열에 담아주기
			
			Arrays.sort(word); // 잘려서 담긴 단어들을 정렬해주기
			
			// 정렬 된 단어를 하나의 단어로 만들기
			String makeword = new String(word);

			// 해당 단어를 셋에 넣기
			set.add(makeword);
		}
		// 셋의 크기를 출력
		System.out.println(set.size());
	}
}