[BOJ 1062] 가르침 (Java)

https://www.acmicpc.net/problem/1062

1062번: 가르침

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main_BOJ_1062 {
	static int N, K;
	static String[] words;
	static boolean[] visited=new boolean[26];
	static int answer=0;
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		N=Integer.parseInt(st.nextToken());
		K=Integer.parseInt(st.nextToken());
		words=new String[N];
		for (int i=0; i<N; i++) {
			words[i]=br.readLine();
		}
		if (K<5) System.out.println(0);
		else {
			visited['a'-'a']=true;
			visited['n'-'a']=true;
			visited['t'-'a']=true;
			visited['i'-'a']=true;
			visited['c'-'a']=true;
			Set<Character> set=new HashSet<>();
			for (int i=0; i<N; i++) {
				for (int j=4; j<words[i].length()-4; j++) {
					char c=words[i].charAt(j);
					if (!visited[c-'a']) set.add(words[i].charAt(j));
				}
			}
			Character[] candidates=set.toArray(new Character[0]);	//antic 외에 새로운 알파벳
			if (candidates.length>0) {
				int target= K-5<=candidates.length ? K-5 : candidates.length;
				comb(0, 0, target, candidates);
			}
			else {
				answer=N;
			}
			System.out.println(answer);
		}

	}
	private static void comb(int start, int cnt, int target, Character[] candidates) {
		if (cnt==target) {
			check();
			return;
		}
		for (int i=start; i<candidates.length; i++) {
			char alphabet=candidates[i];
			visited[alphabet-'a']=true;
			comb(i+1, cnt+1, target, candidates);
			visited[alphabet-'a']=false;
		}
		
	}
	private static void check() {
		int cnt=0;
		for (int i=0; i<N; i++) {
			if (isRight(words[i])) cnt++;
		}
		answer=Math.max(cnt, answer);
	}
	
	private static boolean isRight(String word) {
		for (int i=4; i<word.length()-4; i++) {
			char c=word.charAt(i);
			if (!visited[c-'a']) return false;
		}
		return true;
	}

}

완전탐색 문제.

antic을 먼저 방문처리 해주고, 나머지 K-5 개만큼 뽑는 경우의 수를 구한 후 답을 구해주면 된다. 

나는 단어 중에 나온 알파벳들만 모아서 그 중에서 K-5 개만큼 뽑는 것으로 했는데, 다른 분들의 코드를 보니 따로 모으지 말고 a부터 z까지 이미 방문된거(antic)를 제외하고 K-5개만큼 뽑고 경우를 따져주는 것도 OK 였다.