[백준] 16508 전공책 - 완전탐색 + 문자열(알파벳) JAVA

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

16508번: 전공책

문제풀이

https://gunjoon.tistory.com/100

 

완전탐색 문제입니다.

 

문제의 조건에

- 민호가 만들고자 하는 단어를 의미하는 문자열 T (1 ≤ |T| ≤ 10), 민호가 가진 전공책의 개수를 의미하는 정수 N (1 ≤ N ≤ 16)이 주어진다. 전공책 가격을 의미하는 정수 Ci (10,000 ≤ Ci ≤ 100,000)와 제목을 의미하는 문자열 Wi (1 ≤ |Wi| ≤ 50)가 주어진다. Wi는 항상 대문자이다.

위의 조건을 보고 완전탐색을 돌려도 시간초과가 날것 같지 않다는 생각에 완전탐색을 구현했습니다.

( 아래의 코드에 틀린 코드가 있습니다. )처음에 틀렸었던 이유는 완전탐색을 진행하면서 O(N^2)으로 진행하여 최악의 경우 16^16 의 시간이 주어져서 시간초과가 났습니다.

 

 

 

코드로직입니다.알파벳 26 개의 배열 2개를 선언합니다. ( 알파벳 관련 문제들에 은근히 이런 방식의 접근이 많이 사용되는것 같습니다. )1. T_count[26] : 구하고자하는 문자열의 알파벳의 개수, select_alphabet[26] : 전공책에서 뽑아온 알파벳 개수2. T_count[26]에 구하고자 하는 문자열 알파벳을 T_count[26]에 넣어주기 위해 ++ 처리합니다. (만약 3개라면 3번 더해집니다.)3. 각 전공책을 돌면서 전공책의 모든 알파벳을 select_alphabet[26]에 넣어주기 위해 ++ 처리합니다.

4. 각 전공책을 안넣는 경우도 있기에 select_alphabet[26]을 만나더라도 +0 처리하는 경우도 있습니다. 

5. T_count[26] 의 알파벳 개수보다 select_alphabet[26]의 개수가 더 작은것이 하나라도 존재한다면, 해당 문자열은 완성하지 못합니다.

 

코드

시간초과가 난코드입니다.

완전탐색를 진행하면서 너무 많은 배열과 방문처리를 했기에 시간초과가 납니다.

아래 문제의 시간복잡도를 계산해보면

모든 전공서적 N (최대  16 )의 경우의 수를 16번 모두 16 ^ 16  = 18,446,744,073,709,551,616 이기에 시간초과가 나옵니다. ( 일반적으로 1 억만 넘어가도 나옴 )

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	
	public static String T;
	public static int N;
	public static int price;
	public static int T_index=0;
	public static Node[] Node; 
	public static boolean[][] visited;
	public static Node[] T_Node;
	public static int answer = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	T = st.nextToken();
    	T_Node = new Node[T.length()];
    	
    	st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	Node = new Node[N];
    	visited = new boolean[N][50];
    	
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		int a = Integer.parseInt(st.nextToken());
    		String b = st.nextToken();
    		Node[i] = new Node(a, b, i);
    	}
    	simulate(0);
    	if(answer == Integer.MAX_VALUE)
    		System.out.println("-1");
    	else System.out.println(answer);
    	
    }
    
    public static void simulate(int level) {
//    	System.out.println("======================");
    	if(level == T.length()) {
    		boolean[] temp = new boolean[N];
    		int sum = 0;
    		for(int i=0;i<level;i++) {
    			if(temp[T_Node[i].nodeIndex] == false) {
        			sum += T_Node[i].price;
//        			System.out.println(" "+T_Node[i].price+ " "+T_Node[i].title);
        			temp[T_Node[i].nodeIndex] = true;
    			}
    			
    		}
    		answer = Math.min(answer,  sum);
    		return;
    	}
    	
    	for(int i=0;i<N;i++) {
    		Node temp = Node[i];
    		int price = temp.price;
    		String title = temp.title;
    		if(T_Node[level] != null) continue; //이미 방문한적이 있다면 다음 문자로 넘어감.
    		for(int j=0;j<title.length();j++) {
    			if(visited[i][j] == true) continue;
    			if( T.charAt(level) == title.charAt(j)) {
    				visited[i][j] = true;
    	    		T_Node[level] = temp;
    	    		simulate(level + 1);
    	    		visited[i][j] = false;
    	    		T_Node[level] = null;
    			}
    		}
    	}
    }
}
 
class Node{
	int price;
	String title;
	int nodeIndex;
	public Node(int price, String title, int nodeIndex) {
		this.price = price;
		this.title = title;
		this.nodeIndex = nodeIndex;
	}
}

 

 

정답코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	
	public static String T;
	public static int N;
	public static Node[] Node;
	
	public static int[] T_count = new int[26]; //알파벳 26개
	public static int[] select_alphabet = new int[26]; //알파벳 26개 
	
	public static int answer = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	T = st.nextToken();
    	
    	st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	
    	// T 목표 문자열 ( 민호가 만들고자 하는 문자열 )을 돌면서 문자열의 문자들을 구하기 위해 += 1 처리
    	for(int i=0;i<T.length();i++) {
    		T_count[T.charAt(i) - 'A']++;
    	}
    	Node = new Node[N];
    	
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
        	int a = Integer.parseInt(st.nextToken());
        	String b = st.nextToken();
        	Node[i] = new Node(a, b);	
    	}
    	
    	simulate(0, 0);
    	
    	if(answer == Integer.MAX_VALUE) {
    		System.out.println("-1");
    	}else {
    		System.out.println(answer);
    	}
    }
    
    public static void simulate(int level, int total) {
//    	System.out.println("total:"+total);
    	//만약 모든 전공책을 다 돌았다면
    	if(level == N) {
    		boolean flag = true;
    		//T_count를 통해서 구하고자하는 문자의 개수를 구했고, 그 문자보다 select_alphabet이 모두 커야 해당 문자를 구한 것입니다.
    		for(int i=0; i<26;i++) {
    			if( T_count[i] > select_alphabet[i] ) {
    				flag = false;
    				break;
    			}
    		}
    		
    		if( flag == true) {
    			answer = Math.min(answer,  total); 
    		}
    		return ;
    	}
    	
    	// level 번째의 전공책의 문자열을 돌면서 문자열의 문자들을 모두 방문 처리해줍니다.
    	for(int i=0;i<Node[level].title.length();i++) {
    		//해당 전공책을 읽음처리합니다. 
    		select_alphabet[Node[level].title.charAt(i) - 'A']++;
    	}
    	simulate(level + 1, total + Node[level].price);
    	
    	// level 번째의 전공책을 선택하지 않는다면, 이전 Level에서 위의 코드를 보면 ++ 한 개수를 -- 를 함으로써 다시 선택안한것으로 수정합니다.
    	for(int i=0;i<Node[level].title.length();i++) {
    		select_alphabet[Node[level].title.charAt(i) - 'A']--;
    	}
    	simulate(level + 1, total);
    	
    }
    
   
}
 
class Node{
	int price;
	String title;
	public Node(int price, String title) {
		this.price = price;
		this.title = title;
	}
}