[JAVA] SWEA 9480 - 민정이와 광직이의 알파벳 공부
Solution
- 각 단어마다 포함하는 알파벳을 alphabet배열에 저장해둠
- 1~N개의 단어의 조합을 구하는데 해당 조합이 모든 소문자 알파벳을 포함하는지 확인하고 포함한다면 count증가
Code
import java.util.*;
class Solution
{
private static int count = 0;
public static void main(String args[]) throws Exception
{
Scanner sc = new Scanner(System.in);
StringBuffer sb = new StringBuffer();
int TC = Integer.parseInt(sc.nextLine());
for(int tc=1; tc<=TC; tc++) {
sb.append("#").append(tc).append(" ");
count = 0;
int N = Integer.parseInt(sc.nextLine());
List<String> list = new ArrayList<>();
boolean alphabet[][] = new boolean[N][26];
for(int i=0; i<N; i++){
String word = sc.nextLine();
list.add(word);
for(char j='a'; j<='z'; j++){
if(word.contains(String.valueOf(j))) {
alphabet[i][j-'a'] = true;
}
}
}
for(int i=1; i<=N; i++){
solve(0, 0, i, N, alphabet, new boolean[N]);
}
sb.append(count).append("\n");
}
System.out.println(sb);
}
private static void solve(int i, int size, int max, int N, boolean alphabet[][], boolean check[]){
if(size >= max){
if(isPossible(N, alphabet, check))
count++;
return;
}
if(i >= N){
return;
}
check[i] = true;
solve(i+1, size+1, max, N, alphabet, check);
check[i] = false;
solve(i+1, size, max, N, alphabet, check);
}
private static boolean isPossible(int N, boolean alphabet[][], boolean check[]){
for(char a = 'a'; a <= 'z'; a++){ // 해당 알파벳을 포함하는
boolean isContains = false;
for(int i=0; i<N; i++){ // 단어를 포함했는지 확인
if(alphabet[i][a-'a'] && check[i]){
isContains = true;
break;
}
}
if(!isContains){
return false;
}
}
return true;
}
}
Author And Source
이 문제에 관하여([JAVA] SWEA 9480 - 민정이와 광직이의 알파벳 공부), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gkdud583/JAVA-SWEA-9480-민정이와-광직이의-알파벳-공부저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)