사용한 것
- 가르친 단어들의 조합을 구하기 위한 DFS
- 가르친 단어들을 순서에 상관없이 저장하기 위한 HashSet
add()
와 contains()
의 속도가 O(1)이라서 사용
풀이 방법
K
를 입력 받은 값 - 5로 저장한다. ('a', 'n', 't', 'i', 'c' 는 기본적으로 필요한 글자이기 때문에 제외시킬 것이기 때문이다.)
- 제외한 글자 외 단어들을
words
에 담는다.
K
가 0보다 작으면 기본적인 "antatica"도 만들 수 없으므로 0을 출력한다.
- DFS를 시작한다.
- 가르친 글자들의 조합
learned
에 글자들을 넣으며 depth
를 1씩 증가시킨다.
depth
가 최대로 가르칠 수 있는 K
와 같아지면 몇 개의 단어를 사용할 수 있는지 확인하여 max
보다 크면 갱신한다.
max
를 출력한다.
코드
public class Main {
static Set<Character> learned = new HashSet<>();
static char[] alphabets = {'b', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'o', 'p', 'q',
'r', 's', 'u', 'v', 'w', 'x', 'y', 'z'};
static int N;
static int K;
static String[] words;
static int max = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
String[] split = line.split(" ");
N = Integer.parseInt(split[0]);
words = new String[N];
K = Integer.parseInt(split[1]) - 5;
for (int i = 0; i < N; i++) {
line = br.readLine();
StringBuilder word = new StringBuilder();
for (int j = 0; j < line.length(); j++) {
char c = line.charAt(j);
if (c == 'a' || c == 'n' || c == 't' || c == 'i' || c == 'c') {
continue;
}
word.append(c);
}
words[i] = word.toString();
}
if (K < 0) {
System.out.println(0);
return;
}
dfs(0, -1);
System.out.println(max);
}
static void dfs(int depth, int lastIdx) {
if (depth == K) {
int ct = 0;
for (String word : words) {
boolean contains = true;
for (int i = 0; i < word.length(); i++) {
if (!learned.contains(word.charAt(i))) {
contains = false;
break;
}
}
if (contains) {
ct++;
}
}
if (ct > max) {
max = ct;
}
}
for (int i = lastIdx + 1; i < alphabets.length; i++) {
char c = alphabets[i];
learned.add(c);
dfs(depth + 1, i);
learned.remove(c);
}
}
}