[백준] 1062 가르침 - 백트래킹(BackTracking) + 조합(Combination) JAVA

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

1062번: 가르침

코드설명

백트래킹(BackTracking) + 조합(Combination) 문제입니다.

 

이 문제로직은, 모든 알파벳의 조합을 구한뒤 각 단어들을 순회하면서 최대 단어의 개수를 가져오면 되는 문제입니다.

이때, 모든 알파벳의 조합을 구하기 위해 완전탐색을 진행하면 시간초과가 나므로, 이전까지 어떤 알파벳을 검사했는지 alphabetIndex를 가져가면서 재귀함수를 진행하면 됩니다.

 

 

처음에 틀렸던 방식으로는, 

첫번째 문자열에서 존재하는 alphabet들을 검사한뒤 다음문자열으로 이동,

첫번쩌 문자열에서 존재하는 alphabet들을 검사하지 않은뒤 다음문자열으로 이동. 

이렇게 처리함으로써 모든 경우를 검사했다고 생각했지만,

이와 같은 방법은 두번째 문자열에서 검사한뒤 첫번쨰 문자열로 이동할때가 더 효율적인 경우가 나올 수 있으므로 이 방식은 옳지 않습니다.

이전에 풀었던 스도쿠나 계란으로 계란치기와 같은 문제와는 다른 문제입니다.

해당 문제들은 문제에서 앞에서의 순서가 확실히 정해져있는 문제였기에 아래와 같이 풀어도 되었지만,

이번 문제에서는 앞에서의 순서가 정해지기보다는, 이후의 단어가 앞의 경우에 영향을 끼치므로 모든 경우를 구해야한는 문제입니다.

 

순서는 상관없으니 조합으로 alphabet들을 구하고, 주어진 단어들이 우리가 배운 alphabet들 외의 문자가 들어가 있다면 읽을 수 없는 단어입니다.

코드

배운 단어의 alphabetIndex를 가져가면서 불필요한 연산을 줄인 코드입니다.

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

public class Main {
	public static int K, N;
	public static int answer = 0;
	public static String[] arr;
	public static int[] alphabet;
	public static int cnt = 0;
    public static void main(String[] args) 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());
    	
    	arr = new String[N];
    	alphabet = new int[26];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		arr[i] = st.nextToken(); 
    	}
    	
    	//초기값 세팅
    	alphabet['a' - 'a'] +=1;
    	alphabet['n' - 'a'] += 1;
    	alphabet['t' - 'a'] += 1;
    	alphabet['i' - 'a'] += 1;
    	alphabet['c' - 'a'] += 1;
    	if( K < 5) {
    		System.out.println(answer);
    		return ;
    	}
    	else if( K >= 26) {
    		System.out.println(N);
    		return ;
    	}
    	simulate(0, 5);
    	System.out.println(answer);
    }
    
    public static void simulate(int alphabetIdx, int cnt) {
    	int answerCnt = 0;
    	if(cnt >= K) {
        	for(int i=0;i<N;i++) {
        		boolean findFlag = true;
        		for(int j=4;j<arr[i].length()-4;j++) {
        			if( alphabet[arr[i].charAt(j) - 'a'] == 0) {
        				findFlag = false;
        				break;
        			}
        		}
        		if(findFlag == true) {
        			answerCnt += 1;
        		}
        	}
        	answer = Math.max(answer, answerCnt);
        	return ;
    	}
    	
    	for(int i=alphabetIdx;i<26;i++) {
    		if( alphabet[i] == 0 ) {
    			alphabet[i] = 1;
    			simulate(i, cnt + 1);
    			alphabet[i] = 0;
			}
		}
    	
    }
    
    public static void printAlphabet() {
    	for(int i=0;i<26;i++) {
    		System.out.print(" "+alphabet[i]);
    	}
    	System.out.println();
    }

}

모든경우를 획인하는 코드( 시간초과 )

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

public class Main {
	public static int K, N;
	public static int answer = 0;
	public static String[] arr;
	public static int[] alphabet;
	public static int cnt = 0;
    public static void main(String[] args) 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());
    	
    	arr = new String[N];
    	alphabet = new int[26];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		arr[i] = st.nextToken(); 
    	}
    	
    	//초기값 세팅
    	alphabet['a' - 'a'] +=1;
    	alphabet['n' - 'a'] += 1;
    	alphabet['t' - 'a'] += 1;
    	alphabet['i' - 'a'] += 1;
    	alphabet['c' - 'a'] += 1;
    	if( K - 5 < 0) {
    		System.out.println(answer);
    		return ;
    	}
    	if( K >= 26) {
    		System.out.println(N);
    		return ;
    	}

    	simulate(5);
    	System.out.println(answer);
    }
    
    public static void simulate(int cnt) {
    	
    	int answerCnt = 0;
    	for(int i=0;i<N;i++) {
    		boolean findFlag = true;
    		for(int j=4;j<arr[i].length()-4;j++) {
    			if( alphabet[arr[i].charAt(j) - 'a'] == 0) {
    				findFlag = false;
    				break;
    			}
    		}
    		if(findFlag == true) {
    			answerCnt += 1;
    		}
    	}
    	
    	answer = Math.max(answer, answerCnt);
    	
    	if(K <= cnt)
    		return ;
    	
    	for(int i=0;i<26;i++) {
    		if( alphabet[i] == 0 ) {
    			alphabet[i] = 1;
    			simulate(cnt + 1);
    			alphabet[i] = 0;
			}
		}
    	
    }
    
}

 

 

검증하는 문자열 순서가 정해져있는 코드 ( 이렇게 할경우 모든 경우에 대한 처리가 안됩니다. )

예로들면 1->2->3->4, 2->3->4, 이렇게 되어있어서 2->1->3 이런식으로 처리가 되지 않습니다.

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

public class Main {
	public static int K, N;
	public static int answer = 0;
	public static String[] arr;
	public static int[] alphabet;
	public static int cnt = 0;
    public static void main(String[] args) 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());
    	
    	arr = new String[N];
    	alphabet = new int[27];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		arr[i] = st.nextToken(); 
    	}
    	
    	//초기값 세팅
    	alphabet['a'-'a'] +=1;
    	alphabet['n' - 'a'] += 1;
    	alphabet['t' - 'a'] += 1;
    	alphabet['i' - 'a'] += 1;
    	alphabet['c' - 'a'] += 1;
    	if( K - 5 < 0) {
    		System.out.println(answer);
    		return ;
    	}
    	if( K >= 27) {
    		System.out.println(N);
    		return ;
    	}
//    	printAlphabet();
    	simulate(0, 5);
    	System.out.println(answer);
    }
    
    public static void simulate(int nowIdx, int cnt) {
    	
    	if( K < cnt) {
    		return ;
    	}
    	
//    	printAlphabet();
    	int answerCnt = 0;
    	for(int i=0;i<arr.length;i++) {
    		boolean successFlag = true;
    		for(int j=4; j<arr[i].length() - 4;j++) {
    			if( alphabet[arr[i].charAt(j) - 'a'] == 0 ) { //만약 해당 위치의 알파벳이 존재하지 않다면 못읽은것이므로 실패처리.
    				
    				successFlag = false;
    				break;
    			}
    		}
    		if(successFlag == true) {
//    			System.out.println("CANREAD IDX:"+arr[i]+"IDX:"+i);
    			answerCnt += 1;
    		}
    			
    	}
//    	System.out.println();
    	answer = Math.max(answer,  answerCnt);
    	
    	if(nowIdx >= N) return ; //단어의 개수를 넘어가면 종료시킵니다.
    	
    	int temp = 0;
    	for(int i=4;i<arr[nowIdx].length()-4;i++) { 
    		//만약 'a', 'n', 't', 'i', 'c' 일경우에는 연산할 필요없이 넘어간다.
    		if( arr[nowIdx].charAt(i) == 'a' || arr[nowIdx].charAt(i) == 'n' || arr[nowIdx].charAt(i) == 't' || arr[nowIdx].charAt(i) == 'i' || arr[nowIdx].charAt(i) == 'c') {
    			
    		} else if(alphabet[arr[nowIdx].charAt(i) -'a'] == 0 ){
    			alphabet[arr[nowIdx].charAt(i) - 'a'] += 1;
    			temp += 1;    			
    		}
    	
    	}
    	simulate(nowIdx + 1, cnt + temp);
    	
    	for(int i=4;i<arr[nowIdx].length()-4;i++) { 
    		//만약 'a', 'n', 't', 'i', 'c' 일경우에는 연산할 필요없이 넘어간다.
    		if( arr[nowIdx].charAt(i) == 'a' || arr[nowIdx].charAt(i) == 'n' || arr[nowIdx].charAt(i) == 't' || arr[nowIdx].charAt(i) == 'i' || arr[nowIdx].charAt(i) == 'c') {
    			
    		} else if(alphabet[arr[nowIdx].charAt(i) -'a'] == 1 ){
    			alphabet[arr[nowIdx].charAt(i) - 'a'] -= 1;
    			temp -= 1;    			
    		}
    	}
    	
    	simulate(nowIdx + 1, cnt);
    	
    	
    }
    
    public static void printAlphabet() {
    	for(int i=0;i<26;i++) {
    		System.out.print(" "+alphabet[i]);
    	}
    	System.out.println();
    }

}

 

 

이것 또한 불필요한 탐색을 따로 진행하지 않아, 원활하게 작동합니다.

하지만, 스택함수가 많이 쌓이기에 가장 빠른 코드보다는 최대 30ms 정도 느립니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;
public class Main {
	public static int N, M, K;
	public static Word[] word;
	public static int[] alphabet = new int[26];
	public static int answer = 0;
	public static void main(String[] args) 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());
		
		//a n t i c
		if(K < 5) {
			System.out.println(0);
			return ;
		}
		
		word = new Word[N];
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			String inputWord = st.nextToken();
			
			word[i] = new Word(inputWord);
		}

		K -= 5;
		alphabet['a' - 'a'] = 1;
		alphabet['n' - 'a'] = 1;
		alphabet['t' - 'a'] = 1;
		alphabet['i' - 'a'] = 1;
		alphabet['c' - 'a'] = 1;
		
		selectAlphabet(0, 0, 0);
		
		System.out.println(answer);
	}
	
	public static void selectAlphabet(int level, int selectedCnt, int curAlphabet) {
		if(selectedCnt == K) {
			int cnt = 0;
			for(int i=0; i<N;i++) {
				boolean flag = true;
				for(int j=4;j<word[i].word.length() - 4;j++) {
					if(alphabet[word[i].word.charAt(j) - 'a'] == 1) {
						
					}else {
						flag = false;
						break;
					}
				}
				
				if(flag == true) {
					cnt += 1;
				}else if(flag == false) {
					
				}
				
			}
			
			answer = Math.max(answer, cnt);
			return ;
		}
		
		if(curAlphabet >= 26) {
			return ;
		}
		
		if(alphabet[curAlphabet] == 0) {
			alphabet[curAlphabet] = 1;
			selectAlphabet(level + 1, selectedCnt + 1, curAlphabet + 1);
			alphabet[curAlphabet] = 0;
		}
		selectAlphabet(level + 1, selectedCnt, curAlphabet + 1);
	}

}

class Word{
	String word;
	public Word(String word) {
		this.word = word;
	}
	public Word() {
		
	}
}