시간이 NullNull
[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);
}
}
'알고리즘' 카테고리의 다른 글
[JAVA] [SWEA] 9839. 최고의쌍 (0) | 2020.05.13 |
---|---|
[JAVA] [SWEA] 9940. 순열1 (0) | 2020.05.13 |
[JAVA] [SWEA] 9700. USB 꽂기의 미스터리 (0) | 2020.05.12 |
[JAVA] [SWEA] 9778. 카드 게임 (0) | 2020.05.12 |
[JAVA] [SWEA] 9317. 석찬이의 받아쓰기 (0) | 2020.02.23 |