[백준] code.plus(브루트포스 - 비트마스크,JAVA)1062번, 가르침

문제 링크

1062번: 가르침

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

브루트 포스란.

모든 경우의 수를 대입시켜서 가장 알맞은 경우의 수를 결과로 출력하는 것입니다.

이 문제에 핵심은

1. 남극언어의 시작은 "anta", 끝은 "tica"로 끝난다.

2. K개의 글자만 가르칠 수 있다.

3. 학생들이 K개의 글자를 알았을 때 읽을 수 있는 단어의 최대 개수를 출력한다.

 

학생들이 남극언어를 읽으려면 무조건 "anta"와 "tica"를 읽을 줄 알아야 합니다.

 

K개의 글자를 가르칠 때 항상 'a', 'c', 'i', 'n', 't'를 가르쳐야 합니다.

 'a', 'c', 'i', 'n', 't'를 가르치려면 K≥5이어야 남극 언어로된 단어를 읽을 수 있습니다.

 

K<5

남극 언어로된 단어는 아무것도 읽지 못한다.

출력 : 0

 

K==26

모든 글자를 배운 것으로 모든 단어를 읽을 수 있다.

출력 : 단어의 개수(N)

 

5≤  K < 26

 'a', 'c', 'i', 'n', 't'를 배우고 남은 (K-5)개의 글자의 모든 경우의 수에서 읽을 수 있는 단어의 최대 개수를 구한다.

출력 : 모든 경우에서 최대 값

 

예제입력 1에서는

K = 6

5≤  K < 26

'a', 'c', 'i', 'n', 't'를 배우고 나머지 알파벳 1개를 배울 때

모든 경우의 수에서

'r'을 배웠을 때 2개의 단어를 읽을 수 있어서

모든 경우의 최대값인 2가 출력됩니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 N, K을 저장하였습니다.
• 'a', 'c', 'i', 'n', 't'이 사용되었다고 초기화하는 alphabetInit()함수를 실행하였습니다.
• K의 값에 따라 cal함수를 실행하거나 N이나 0을 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• cal함수는 재귀를 통해 배울 수 있는 알파벳의 모든 경우의 수를 구합니다.
• wordCheck함수는 배운 알파벳으로 남극 언어를 몇 개 읽을 수 있는지 확인하고 최대값을 구합니다.
• alphabetInit으로 'a', 'c', 'i', 'n', 't'의 알파벳을 배웠다고 초기화합니다.

 

import java.io.*;
import java.util.*;
public class Main {
	static int N,K,result = Integer.MIN_VALUE;
	static boolean[] alphabet = new boolean[26];	//배운 알파벳 확인 배열
	static ArrayList<String> word = new ArrayList<>();	//입력되는 단어 저장 리스트
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        	//입력값 처리하는 BufferedReader
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        	//결과값 출력하는 BufferedWriter
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		alphabetInit();	//'a', 'c', 'i', 'n', 't' 배웠다고 초기화
		if(K<5)		//배울 수 있는 글자가 5개 이하일 때
			bw.write("0");
		else if(K==26)	//배울 수 있는 글자가 26개일 때
			bw.write(N + "\n");
		else {		//그 사이일 때
        	//입력되는 남극 언어 저장
			for(int i=0;i<N;i++) {
				String temp = br.readLine();
				temp.replace("anta", "");
				temp.replace("tica", "");
				word.add(temp);
			}
			cal(1,5);	//모든 경우의 수에서 읽을 수 있는 단어 최대 수 구하는 함수
			bw.write(result + "\n");	//최대값 BufferedWriter 저장
		}
		bw.flush();		//결과 출력
		bw.close();
		br.close();
	}
    	//재귀로 알파벳을 배우는 모든 경우를 구하는 함수
	static void cal(int alpha,int cur) {
		if(cur==K) {
			wordCheck();
			return ;
		}
		for(int i=alpha;i<26;i++) {
			if(alphabet[i])
				continue;
			alphabet[i] = true;
			cal(i,cur+1);
			alphabet[i] = false;
		}
		return;
	}
    	//배운 알파벳으로 단어를 몇 개 읽을 수 있는지 확인하는 함수
	static void wordCheck() {
		int count = 0;
		for(int i=0;i<word.size();i++) {
			String temp = word.get(i);
			boolean ck = false;
			if(!temp.equals("")) {
				int size = temp.length();
				for(int j=0;j<size;j++) {
					if(!alphabet[temp.charAt(j)-97]) {
						ck = true;
						break;
					}
				}
			}
			if(!ck)
				count++;
		}
		result = Math.max(result, count);
		return;
	}
    	//'a', 'c', 'i', 'n', 't'가 배웠다고 초기화하는 함수
	static void alphabetInit() {
		alphabet[0] = alphabet[2] = alphabet[8] = alphabet[13] = alphabet[19] = true;
		return;
	}
}