[BOJ]1062_가르침_JAVA

--문제--

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

1062번: 가르침

--문제 접근--

첫 번째 접근 방법..

쉽게 접근해 봤습니다.

맨 처음 anta / tica는 무조건 포함해야 되므로 

antic는 무조건 포함시킨 후 시작되어야 한다고 생각하였고, 

그 이후는 하나씩 검사를 하여 알파벳이 하나라도 가지고 있다면 그 이후 알파벳을 검사해보는 DFS방식으로 해봤는데 시간 초과가 났습니다.

 

시간초과가 난 코드를 알파벳을 돌면서 검사를 할 때에 전에 검사했던 부분부터 시작을 함으로 시간 초과를 막을 수 있었습니다.

그리고 알파벳 검사 부분에서 계속 틀렸습니다가 나와 수정을 하여 정답을 맞혔습니다.

어찌 보면 크게 보면 조합 코드인 것으로 보입니다.

--성공코드--

package 준비운동;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BOJ_1062_가르침 {
	static int N,K,ans;
	static String[] arr;
	static boolean[] check=new boolean[26];
	static boolean[] leng;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		K=sc.nextInt();
		ans=0;
		leng=new boolean[N];
		K-=5;
		if(K<0) {
			System.out.println(0);
			System.exit(0);
		}
		arr=new String[N];
		for(int i=0;i<N;i++) {
			arr[i]=sc.next();
		}
		check['a'-'a']=true;
		check['n'-'a']=true;
		check['t'-'a']=true;
		check['i'-'a']=true;
		check['c'-'a']=true;
		for(int i=0;i<N;i++) {
			String sen=arr[i];
			String tmp="";
			for(int j=0;j<sen.length();j++) {
				if(!check[sen.charAt(j)-'a']) {
					tmp+=sen.charAt(j);
				}		
			}
			arr[i]=tmp;
		}
		for(int i=0;i<N;i++) {
			if(arr[i].length()==0)leng[i]=true;
			System.out.println(arr[i]);
		}
		
		DFS(0,0);
		System.out.println(ans);
	}
	private static void DFS(int level,int start) {
		if(level==K) {
			int tmp=0;
			for(int i=0;i<N;i++) {
				boolean CheckV=true;
				for(int j=0;j<arr[i].length();j++) {
					if(!check[arr[i].charAt(j)-'a']) {
						CheckV=false;
						break;
					}
				}
				if(CheckV)tmp++;
			}
			ans=Math.max(ans, tmp);
			return;
		}
		
		for(int i=start;i<26;i++) {
			if(!check[i]) {
				check[i]=true;
				DFS(level+1,i);
				check[i]=false;
		}
		
	}
	}
	}

--실패 코드--

package 준비운동;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BOJ_1062_가르침 {
	static int N,K,ans;
	static String[] arr;
	static boolean[] check=new boolean[26];
	static boolean[] leng;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		K=sc.nextInt();
		ans=0;
		leng=new boolean[N];
		K-=5;
		if(K<0) {
			System.out.println(0);
			System.exit(0);
		}
		arr=new String[N];
		for(int i=0;i<N;i++) {
			arr[i]=sc.next();
		}
		check['a'-'a']=true;
		check['n'-'a']=true;
		check['t'-'a']=true;
		check['i'-'a']=true;
		check['c'-'a']=true;
		for(int i=0;i<N;i++) {
			String sen=arr[i];
			String tmp="";
			for(int j=0;j<sen.length();j++) {
				if(!check[sen.charAt(j)-'a']) {
					tmp+=sen.charAt(j);
				}		
			}
			arr[i]=tmp;
		}
		for(int i=0;i<N;i++) {
			if(arr[i].length()==0)leng[i]=true;
		}
		DFS(0);
		System.out.println(ans);
	}
	private static void DFS(int level) {
		if(level==K) {
			int tmp=0;
			for(int i=0;i<N;i++) {
				if(leng[i])tmp++;
			}
			ans=Math.max(tmp, ans);
			return;
		}
		
		for(int i=0;i<26;i++) {
			if(!check[i]) {
				check[i]=true;
				Queue<Integer> tmp=new LinkedList<>();
				for(int j=0;j<N;j++) {
					if(leng[j])continue;
					String sen=arr[j];
					String temp="";
					for(int k=0;k<sen.length();k++) {
						if(!check[sen.charAt(k)-'a']) {
							temp+=sen.charAt(k);
						}else {
							tmp.add(j);
						}
					}
					if(temp.length()==0) {
						leng[j]=true;
					}
					arr[j]=temp;
				}
				if(tmp.size()>0) {
					DFS(level+1);
					for(int q=0;q<tmp.size();q++) {
						int poll=tmp.poll();
						if(arr[poll].length()==0)leng[poll]=false;
						String sentence=arr[poll];
						sentence+=(char)(i+'a');
						arr[poll]=sentence;
					}
				}
				check[i]=false;
			}
		}
		
	}

}