[종만북][알고스팟] Restore, 실험 데이터 복구하기 - 동적계획법(Dynamic Programming, DP) + 비트마스킹(BitMask) + 완전탐색(BruteForce) JAVA

https://www.algospot.com/judge/problem/read/RESTORE

algospot.com :: RESTORE

코드설명

동적계획법(Dynamic Programming, DP) + 비트마스킹(BitMask) + 완전탐색(BruteForce) 를 활용합니다.

 

문제에서 어려웠던점은 reconstruct 함수로 최대값을 Construct, 즉, 실제로 출력하는 방법입니다.

next를 사용했을경우의 답이 restore했던 값과 같다면, 해당 단어를 선택하는 것이 최선의 선택입니다.

코드

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	private static int C, N, W, H, K;
    private static int answer = 0;
    private static String[] word;
    private static int[][] cache, overlap;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        C = Integer.parseInt(st.nextToken());
        while(C-- > 0){
        	st = new StringTokenizer(br.readLine());
        	K = Integer.parseInt(st.nextToken());
        	
        	word = new String[K];
        	cache = new int[K][1<<K]; //왜 1<<N으로 하지? 순열 개수 아닌가? 3!
        	overlap = new int[K][K];
        	
        	for(int i=0;i<K;i++) {
        		Arrays.fill(cache[i], -1);
        	}
        	
        	for(int i=0;i<K;i++) {
        		st = new StringTokenizer(br.readLine());
        		word[i] = st.nextToken();
        	}
        	
        	precalcOverLap();
        	
//        	System.out.println();System.out.println();System.out.println();
//        	for(int i=0;i<K;i++) {
//        		for(int j=0;j<K;j++) {
//        			System.out.print(overlap[i][j]+" ");
//        		}
//        		System.out.println();
//        	}
 
        	String answer = "";
        	for(int i=0;i<K;i++) {
        		if(overlap[i][i] != -1) {
        			
        			String ret = word[i] + reconstruct(i, (1<<i));
        			
        			if(answer.equals("")) {
        				answer = ret;
        			} else if(answer.length() > ret.length()){
        				answer = ret;
        			}
        		}
        	}
        	System.out.println(answer);
        	
        	
        }
        
    }
    
    private static int restore(int last, int used) {
    	if(used == (1<<K) - 1) return 0;
    	
    	if(cache[last][used] != -1) return cache[last][used];
    	int ret = 0;
    	for(int next =0; next < K; next++) {
    		if( ((used & 1<<next) == 0) && overlap[last][next] != -1) {
    			int cand = overlap[last][next] + restore(next, used + (1<<next));
    			ret = Math.max(ret, cand);
    		}
    	}
    	return cache[last][used] = ret;
    }
    
    private static String reconstruct(int last, int used) {
    	//기저사례:
    	if(used == (1<<K) - 1) return "";
    	//다음에 올 문자열 조각을 찾는다.
    	for(int next = 0; next < K; next++) {
    		//next가 이미 사용되었으면 제외, overlao[last][used] 완전히 겹치는 경우가 존재한다면 무시.
    		if( ((used) & (1 << next)) > 0 || overlap[last][next] == -1) {
//    			System.out.println("continue because lastnext");
    			continue;
    		}
    		
    		//next를 사용했을경우의 답이 최적해와 같다면 next를 사용한다.
    		int ifUsed = restore(next, used + (1<<next)) + overlap[last][next];
    		if(restore(last, used) == ifUsed) {
    			return (word[next].substring(overlap[last][next]) + reconstruct(next, used + (1<<next)));
    		}
    	}
    	return "";
    }
 
    
    private static void precalcOverLap() {
    	for(int i=0; i<K; i++) {
    		for(int j=0;j<K;j++) {
    			if(i == j) continue;
    			if(overlap[i][j] == -1) continue;
    			//i번쨰 단어와 j번쨰 단어를 비교하자.
    			
    			//만약 하나의 문자열에 아예 포함되어 있다면, overlap[i][j] == -1로 바꾼다.
    			if(word[i].contains(word[j])) {
    				for(int h=0; h<K;h++) {
    					overlap[h][j] = -1;
    					overlap[j][h] = -1;
    				}
    				continue;
    			}
    			
    			
    			//1. 먼저 더 작가너 같은 길이의 단어가 해당 문자열을 순회하면서 일치하는지 찾을 것 이다.
    			//최대값을 반환해주어야 하니, len을 1부터가 아닌 겹칠 수 있는 최대길이부터 시작합니다.
    			for(int len = Math.min(word[i].length(), word[j].length()); len > 0; len--) {
    				if(word[i].substring(word[i].length() - len).equals(word[j].substring(0, len))) {
    					overlap[i][j] = len;
    					break;
    				}
    			}
    			
    		}
    	}
    }
}