백준 1062 가르침

조합으로 풀 수 있는 문제다.

단어는 무조건 anta와 tica가 포함되므로 가르쳐야 할 알파벳에 a,c,i,n,t 를 기본으로 저장해준다. boolean[26] 배열로 알파벳의 사용여부를 체크할 수도 있지만 나는 비트의 자리수를 체크해 알파벳이 사용됐는지 안됐는지를 체크해줬다.

• flag에 a,c,i,n,t를 사용해줘야하니 각 자리를 1로 표기한다.
• K가 5보다 작으면 애초에 읽을 단어가 없으니 0, K가 26이면 전부 읽을 수 있으니 N으로 예외처리를 해줬다.
• flag를 이용해 선택할 알파벳 K-5개를 뽑음. 
• 다 뽑으면 각 단어의 알파벳을 하나씩 체크하며 현재 뽑은 단어로 단어를 만들 수 있는지 확인한다. 어차피 단어는 앞에 4개, 뒤에 4개는 볼 필요 없으므로 범위설정을 4 ~ word.length()-4까지만 해준다.

처음에 계속 시간초과나서 뭐가 문젤까 고민했는데 K==26일때 N을 출력하는 코드를 쓰니까 해결됐다. 완탐으로 풀땐 예외처리가 굉장히 중요하다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	/**
	 * 백준 1062 가르침 
	 * */
	static int N, K;
	static String[] words;
	static int max = 0;
	
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
//		in = new BufferedReader(new StringReader(input));
		
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		words = new String[N];
		
		for(int i=0; i<N; i++) {
			words[i] = in.readLine();
		}
		
		int flag = 0;
		flag = 1<<0 | 1<<2 | 1<<8 | 1<<13 | 1<<19;		//a,c,i,n,t
		
		if(K < 5) {
			System.out.println(0);
		}
		else if(K == 26) {
			System.out.println(N);
		}
		else {
			findWord(5, 0, flag);
			System.out.println(max);
		}
			
	}
	
	private static void findWord(int cnt, int start, int flag) {
		if(cnt == K) {
			int result = 0;
			for(int i=0; i<N; i++) {
				String word = words[i];
				int j=4, end = word.length()-4;
				for( ;j<end; j++) {
					if((flag & 1 << (word.charAt(j)-'a')) == 0)
						break;
				}
				if(j == end)
					result++;
			}
			max = Math.max(result, max);
			return;
		}
		for(int i=start; i<26; i++) {
			if((flag & 1<<i) == 1)	continue;
			findWord(cnt+1, i+1, flag | 1<<i);
		}
	}
	
	
	static String input ="9 8\n" + 
			"antabtica\n" + 
			"antaxtica\n" + 
			"antadtica\n" + 
			"antaetica\n" + 
			"antaftica\n" + 
			"antagtica\n" + 
			"antahtica\n" + 
			"antajtica\n" + 
			"antaktica";
}