[Java/자바 백준 1062] 가르침

풀이

문제 해석이 어려웠던 문제.

알파벳 K개를 가르칠 때 N개 단어 중 최대로 읽을 수 있는 개수를 정해주는 문제

"anta"로 시작해서 "tica"로 끝나기 때문에

a,n,t,i,c 5개 알파벳은 꼭 있어야 하므로 K는 5개 이상 이어야합니다.

 

그 다음 조합으로 풀고, 이중 for문을 통해 단어를 읽을 수 있으면 +1 시켜주어서 max값으 비교했습니다.

import java.io.*;
import java.util.*;

public class Main{
	static int N, K, max;
	static boolean[] isSelected = new boolean[26];
	static String[] strArr;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		if(K < 5) {
			System.out.println(0);
			return;
		}else if(K == 26) {
			System.out.println(N);
			return;
		}
		else {		
			strArr = new String[N];
			for(int i = 0 ; i < N ; i++) {
				String tmp = br.readLine();
				strArr[i] = tmp.substring(4, tmp.length()-4);
			}
			isSelected['a'-97] = true;
			isSelected['n'-97] = true;
			isSelected['t'-97] = true;
			isSelected['i'-97] = true;
			isSelected['c'-97] = true;
			K -= 5;
			combination(0,0);
			System.out.println(max);
		}
	}
	private static void combination(int start, int cnt) {
		if(max == N) {
			return;
		}
		if(cnt == K) {
			int flagCnt = 0;
			for(int i = 0 ; i < N ; i++) {
				boolean flag = true;
				for(int j = 0 ; j < strArr[i].length() ; j++) {
					if(!isSelected[strArr[i].charAt(j) - 97]) {
						flag = false;
						break;
					}
				}
				if(flag == true) {
					flagCnt ++;
				}
			}
			max = Math.max(max, flagCnt);
			return;
		}
		
		for(int i = start ; i < 26 ; i++) {
			if(!isSelected[i]) {
				isSelected[i] = true;
				combination(i+1, cnt+1);
				isSelected[i] = false;
			}
		}
	}
}