[D3] 민정이와 광직이의 알파벳 공부 - 9480
성능 요약
메모리: 94,852 KB, 시간: 256 ms, 코드길이: 990 Bytes
제출 일자
2023-11-12 15:08
출처: SW Expert Academy, https://swexpertacademy.com/main/code/problem/problemList.do
import java.util.Scanner;
class Solution {
public static int answer;
public static void main(String args[]) throws Exception {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int tc = 1; tc <= T; tc++) {
int n = sc.nextInt();
answer = 0;
String[] words = new String[n];
boolean[] visit = new boolean[n];
for (int i = 0; i < n; i++) {
words[i] = sc.next().toLowerCase();
}
combination(0, n, words, visit);
System.out.println("#" + tc + " " + answer);
}
}
private static boolean check(String[] words, boolean[] visit) {
int[] alpha = new int[26];
for (int i = 0; i < words.length; i++) {
if (visit[i]) {
for (char ch : words[i].toCharArray()) {
alpha[ch - 'a']++;
}
}
}
for (int i = 0; i < 26; i++) {
if (alpha[i] == 0) {
return false;
}
}
return true;
}
private static void combination(int start, int end, String[] words, boolean[] visit) {
if (start == end) {
if (check(words, visit)) {
answer++;
}
return;
}
visit[start] = true;
combination(start + 1, end, words, visit);
visit[start] = false;
combination(start + 1, end, words, visit);
}
}
조합과 배열을 이용한 풀이이다. HashSet을 이용하면 더 간단하게 가능
import java.util.*;
class Solution {
public static int answer,n;
public static void main(String args[]) throws Exception {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int tc = 1; tc <= T; tc++) {
n = sc.nextInt();
answer = 0;
String[] words = new String[n];
for (int i = 0; i < n; i++) {
words[i] = sc.next().toLowerCase();
}
combination(0,words,new HashSet<Character>());
System.out.println("#" + tc + " " + answer);
}
}
private static void combination(int depth, String[] words, HashSet<Character> s) {
HashSet<Character> hs = new HashSet<>(s);
if (depth == n) {
if(hs.size() == 26) answer++;
return;
}
combination(depth+1, words, hs);
for(char ch : words[depth].toCharArray()){
hs.add(ch);
}
combination(depth+1, words, hs);
}
}
'알고리즘 - SWEA > D3' 카테고리의 다른 글
[SW expert Academy] SWEA 10032번 과자 분배 자바(Java) (0) | 2023.11.12 |
---|---|
[SW expert Academy] SWEA 7732번 시간 개념 자바(Java) (0) | 2023.11.12 |
[SW expert Academy] SWEA 5642번 [Professional]합 자바(Java) (0) | 2023.11.10 |
[SW expert Academy] SWEA 3260번 두 수의 덧셈 자바(Java) (0) | 2023.11.10 |
[SW expert Academy] SWEA 3809번 화섭이의 정수 나열 자바(Java) (0) | 2023.11.10 |