[BaekJoon] 1062 가르침 (Java)

1.  문제 링크

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

2.  문제

요약

• 남극에 사는 김지민 선생님은 학생들에게 K개의 글자를 가르칠 시간 밖에 없습니다.
• 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있습니다.
• 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 알고 싶어합니다.
• 남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝나며, 남극언어에 단어는 N개 밖에 없다고 가정합니다.
• K개의 글자를 가르칠 때 학생들이 읽을 수 있는 단어의 최댓값을 구하는 문제입니다.
• 입력: 첫 번째 줄에 50보다 작거나 같은 자연수인 단어의 개수 N, 26보다 작거나 같은 자연수 또는 0인 K가 주어지고 두 번째 줄부터 N개의 줄에 남극 언어의 단어가 주어집니다.
  • 단어는 영어 소문자로만 이루어져 있습니다.
  • 길이가 8보다 크거나 같고, 15보다 작거나 같습니다.
  • 모든 단어는 중복되지 않습니다.
• 출력: 첫 번째 줄에 김지민이 K개의 글자를 가르칠 때, 학생들이 읽을 수 있는 단어 개수의 최댓값을 출력합니다.

3.  소스코드

백트래킹

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

public class Main {
	static int N, K, possibleWords;
	static String[] words;
	static boolean[] alphabets;
	static void input() {
		Reader scanner = new Reader();
		N = scanner.nextInt();
		K = scanner.nextInt();
		words = new String[N];		
		for(int word = 0; word < N; word++) {
			String temp = scanner.nextLine();
			temp = temp.replace("anta", "");
			temp = temp.replace("tica", "");
			words[word] = temp;
		}
		alphabets = new boolean[26];
		alphabets['a' - 'a'] = true;
		alphabets['n' - 'a'] = true;
		alphabets['t' - 'a'] = true;
		alphabets['i' - 'a'] = true;
		alphabets['c' - 'a'] = true;
		possibleWords = 0;
	}
	
	static void solution() {
		if(K < 5) {
			System.out.println(0);
			return;
		}
		if(K == 26) {
			System.out.println(N);
			return;
		}
		rec_func(0, 0);
		System.out.println(possibleWords);
	}
	
	static void rec_func(int idx, int depth) {
		if(depth == K - 5) {
			int num = 0;
			for(int word = 0; word < N; word++) {
				boolean flag = true;
				for(int index = 0; index < words[word].length(); index++) {
					if(!alphabets[words[word].charAt(index) - 'a']) {
						flag = false;
						break;
					}
				}
				if(flag) num++;
			}
			possibleWords = Math.max(possibleWords, num);
		}
		
		for(int index = idx; index < 26; index++) {
			if(!alphabets[index]) {
				alphabets[index] = true;
				rec_func(index + 1, depth + 1);
				alphabets[index] = false;
			}
		}
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch(IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}
}

비트마스킹 및 백트래킹

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

public class Main {
	static int N, K, possibleWords, flag;
	static String[] words;
	static void input() {
		Reader scanner = new Reader();
		N = scanner.nextInt();
		K = scanner.nextInt();
		words = new String[N];		
		for(int word = 0; word < N; word++) {
			String temp = scanner.nextLine();
			temp = temp.replace("anta", "");
			temp = temp.replace("tica", "");
			words[word] = temp;
		}
		possibleWords = 0;
		flag = 0;
		flag |= 1 << ('a' - 'a');
		flag |= 1 << ('n' - 'a');
		flag |= 1 << ('t' - 'a');
		flag |= 1 << ('i' - 'a');
		flag |= 1 << ('c' - 'a');
	}
	
	static void solution() {
		if(K < 5) {
			System.out.println(0);
			return;
		}
		if(K == 26) {
			System.out.println(N);
			return;
		}
		rec_func(0, 0, flag);
		System.out.println(possibleWords);
	}
	
	static void rec_func(int idx, int depth, int flag) {
		if(depth == K - 5) {
			int num = 0;
			for(int word = 0; word < N; word++) {
				boolean isValid = true;
				for(int index = 0; index < words[word].length(); index++) {
					if((flag & 1 << words[word].charAt(index) - 'a') == 0) {
						isValid = false;
						break;
					}
				}
				if(isValid) num++;
			}
			possibleWords = Math.max(possibleWords, num);
		}
		
		for(int index = idx; index < 26; index++) {
			if((flag & 1 << index) == 0)
				rec_func(index + 1, depth + 1, flag | 1 << index);
		}
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch(IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}
}