1062_가르침 **

사용 알고리즘: 백트래킹

사용 언어: java

 

package week03;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.StringTokenizer;

/**
 * 중복되는 알파벳은 최대한 피해보려고 HashSet을 썼지만
 * 사용 미숙의 문제로 망해버림
 */

public class Main_bj_1062_가르침 {
	static int n, k; //단어의 개수, 알려줄 알파벳 수
	static String[] words;
	static boolean[] alpha = new boolean[26]; //알파벳은 26자
	static int ans = 0; //답
	
	public static void main(String[] args) throws IOException {
		input_1062();
		
		if(k < 5) {
			System.out.println(0);
		}
		else if(k >= 26) {
			System.out.println(n);
		}
		else {
			backtrack_1062(0, 5); //방문 배열의 확인할 인덱스, 여태배운 알파벳의 수
			System.out.println(ans);
		}
	}

	private static void backtrack_1062(int idx, int learn) {
		if (k == learn) {
			int cnt = 0;
			
			for (int i =0; i < n; i++) {
				String word = words[i];
				if ( canRead(word) ) cnt++;
			}
			
			ans = Math.max(ans, cnt);
			return;
		}
		
		for (int i=idx; i<26; i++) {
			if(!alpha[i]) {
				alpha[i] = true;
				backtrack_1062(i+1, learn+1);
				alpha[i] = false;
			}
		}
	}

	private static boolean canRead(String word) {
		for (int i=0; i<word.length(); i++) {
			if(!alpha[word.charAt(i) -'a']) return false;
		}
		return true;
	}

	private static void input_1062() 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();
		}
		
		//접두사, 접미사 다섯 문자는 무조건 알아야 함
		alpha['a' - 'a'] = true;
		alpha['c' - 'a'] = true;
		alpha['i' - 'a'] = true;
		alpha['n' - 'a'] = true;
		alpha['t' - 'a'] = true;
	}

}

 

set을 사용했다가 iterator를 사용했다가 arraylist를 사용했다가....