[백준 1062번] 가르침 - java

문제 설명

1. 전체 단어 N, 가르칠 수 있는 글자 K가 주어진다.

2. 모든 단어는 'anta'로 시작되고, 'tica'로 끝난다.

3. 학생이 배울 수 있는 최대 단어의 개수를 return한다.

 

 

풀이 과정

 1. 먼저 'a', 'n', 't', 'i', 'c' 다섯 글자는 공통적으로 들어가야 한다.

 2. 기준을 글자로 잡고, 글자들에 따라 배울 수 있는 단어들을 return하면 될 것이다.

 3. 예를 들어 7글자를 가르치고, 3개의 단어라고 한다면 

   ex ) - 위의 5글자는 무조건 배우게 된다.

         - 따라서 추가로 2글자를 더 배우는 모든 경우를 구하면 될 것이다.

 

         a~z까지 확인하여 배우지 않은 경우 가르친다.

         1 - 'a' 'b' 'c' 'd' 'n' 't' 'i'

         2 - 'a' 'b' 'c' 'e' 'n' 't' 'i'  

         3 - 'b'로 진행하는 경우 모두 수행

         4 - 'a' 'c' 'e' 'f' 'n' 't' 'i'

         5 - 이런 식으로 K(여기서는 5개를 이미 배우니 K-5) 개의 숫자만큼 배우지 않은 단어들을 배우며, 해당 단어가 있으면 check하면 될 것이다.

 4. 이렇게 해서 구한 방법 중 가장 큰 값 return한다.

 

코드

	import java.util.*;
	public class Main {
	public static int N;
	public static int K;
	// 체크할 알파벳의 개수 = a~z까지 26개
	public static boolean[] check = new boolean[26];
	public static String[] word;
	public static int ans = 0;
	public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
	N = sc.nextInt();
	K = sc.nextInt();
	word = new String[N];
	for(int i=0; i<N; i++)
	word[i] = sc.next();
	// 먼저 입력을 모두 받고, 남극 문자는 앞의 5개를 최소한 배워야 한다. 따라서 K는 5를 빼주어, 무조건 배우는 5자를 고려해 준다.
	K -= 5;
	// 해당 알파뱃들은 무조건 배워야 하기 때문에 해당하는 위치를 true해 준다. 즉 모든 글자에 공통으로 들어간다는 뜻이다.
	check['a'-'a'] = true;
	check['t'-'a'] = true;
	check['n'-'a'] = true;
	check['i'-'a'] = true;
	check['c'-'a'] = true;
	DFS(0, 0);
	System.out.println(ans);
	}
	// DFS는 시작위치와 현재까지 카운트를 생각한다.
	public static void DFS(int start, int count) {
	// 현재 DFS level이 배울 수 있는 글자 개수 K개에 도달한 경우
	if ( count == K ) {
	// 현재까지의 값을 저장할 now를 선언한다.
	int now = 0;
	// 모든 문자에 대해 생각해 준다.
	for(int i=0; i<N; i++) {
	// 모든 문자가 현재까지 check한 알파뱃으로 만들 수 있으면 'can'이 true, 만들 수 없으면 false이다.
	boolean can = true;
	// 현재 문자의 길이까지 알파뱃을 판단하여 만들 수 없으면 false를 return하면 된다.
	for(int j=0; j<word[i].length(); j++) {
	if( !check[word[i].charAt(j)-'a'] ) {
	can = false;
	break;
	}
	}
	// 해당 문자를 만들 수 있으면 now가 하나 늘어난다.
	if( can )
	now++;
	}
	// 이렇게 해당 count까지 판단한 DFS의 마지막 확인에서 만들 수 있다고 판단한 단어가 현재 최대값보다 많으면 바꾸어 준다.
	if( ans < now ) {
	ans = now;
	return;
	}
	}
	// 0~26까지 모두 확인, 자기 시작점부터 맨 뒤까지, 또 그 시작점부터 맨 뒤까지...이렇게 하면 K개의 단어를 배우는 모든 경우를 탐색 가능하다.
	for(int i=start; i<26; i++) {
	if( !check[i] ) {
	check[i] = true;
	DFS(i, count+1);
	check[i] = false;
	}
	}
	}
	}

view raw 가르침 hosted with ❤ by GitHub