[JAVA] [SWEA] 9480. 민정이와 광직이의 알파벳 공부

아기 광직이는 열심히 받아쓰기를 했지만, 아직 알파벳을 다 떼지 못했다.

아기 민정이는 그런 광직이가 반 친구들에게 놀림 받지 않을까 걱정이 되어 직접 학습지를 만들어 광직이에게 알파벳을 가르쳐 주려고 한다.

(아기 민정이는 광직이보다 동생이지만, 알파벳을 잘 알고 있다.)

민정이는 광직이가 따라 적을 수 있도록 알파벳 연습용 단어 세트를 여러 개 만들 것이다.

광직이는 현재 N개의 영어 단어를 알고 있고, 이 중 몇 개를 골라 하나의 세트로 만드는데, 각 세트 안에 포함된 단어의 순서는 중요하지 않다.

광직이가 모든 알파벳을 골고루 공부할 수 있도록, 단어 세트에는 26개의 알파벳 소문자가 모두 포함되어 있어야 한다.

즉, 모든 알파벳 소문자에 대해, 단어 세트 안에 그 문자를 포함하는 단어가 적어도 하나 존재해야 한다.

단어 세트가 많이 있을수록 광직이가 알파벳을 더 잘 외울 것이라 생각한 민정이는 서로 다른 세트를 최대한 많이 만들어 주려고 한다.

아기 민정이가 광직이를 위해 몇 개의 단어 세트를 만들 수 있을지 구해주자!

 

 

 

문제부터가 이상하다 지금은 문제가 약간 수정이 되었는데

 

초기에는 인물도 이상하였고 무슨 말인지 이해하기가 힘들었다.

 

결론부터 말하자면, 이 문제는

 

1. 주어진 단어들로 조합을 구하여

 

2. 그 단어들이 a~z가 다 포함되는 경우에 갯수를 추가해주면 된다.

 

조합의 경우 그냥 간단하게 dfs로 넣고 안넣고를 하였고,

 

마지막에 기저영역에서 a~z가 다 포함되었는지를 체크하였다.

 

a~z가 중복으로 들어간 경우도 있기 때문에 a~z가 다 들어갔는지 체크하는 배열의 경우

 

integer로하여 중복을 허용해주었고

 

느리더라도 확실한 방법을 택하였다.

 

전체 코드를 본다면 너무 간단하여 다 알 수 있을 것이다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Solution9480 {
	static int result;
	public static void main(String[] args) throws Exception{		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = Integer.parseInt(br.readLine());
		for(int t=1; t<=T; ++t) {
			int n = Integer.parseInt(br.readLine());
			result = 0;
			boolean[][] arr = new boolean[n][26];
			for(int i=0; i<n; ++i) {
				char[] str = br.readLine().toCharArray();
				for(int j=0; j<str.length; ++j) {
					arr[i][str[j]-'a'] = true;
				}
			}
			dfs(0, n, arr, new int[26]);
			bw.write("#"+t+" "+result+"\n");
		}
		bw.close();
		br.close();
	}
	
	static void dfs(int depth, int cnt, boolean[][] arr, int[] check) {
		if(depth == cnt) {
			int flag = 0;
			for(int i=0; i<check.length; ++i) {
				if(check[i] >= 1) {
					++flag;
				}
			}
			if(flag == 26) {
				++result;
			}
			return;
		}
		
		
		for(int j=0; j<arr[depth].length; ++j) {
			if(arr[depth][j]) {
				++check[j];
			}
		}
		dfs(depth+1, cnt, arr, check);
		for(int j=0; j<arr[depth].length; ++j) {
			if(arr[depth][j]) {
				--check[j];
			}
		}
		dfs(depth+1, cnt, arr, check);
		
	}
}