[AlgoSpot] 실험 데이터 복구하기

문제 설명

알고리즘 문제 해결 전략 - 동적 계획법
https://algospot.com/judge/problem/read/RESTORE

문제 풀이

• 동적 계획법 문제이다.
• 문제 풀이는 다음과 같다.

  1. 특정 문자열에 포함되는 문자열들 제거해줌.
  2. solve(index, bitMask) : index번째 문자열을 시작으로하고, bitMask만큼 문자열들이 남았을 때, 최소 길이 문자열을 리턴한다.

  • solve(index, bitMask) = MIN(index문자열 과 K문자열 겹치는 부분 제외 index문자열 앞부분 + solve(K, bitMask(K제거)))
  • index문자열 과 K문자열 겹치는 부분 제외 index문자열 앞부분의 경우 미리 계산해놓고 중복 계산을 막아준다.

소스 코드 (JAVA)

import java.util.Scanner;

public class Main {
    public static int C, K;
    public static String[] subString = new String[16];
    public static String[][] dp = new String[16][1<<16];
    public static String[][] shortestString = new String[16][16];
    public static boolean[] erase = new boolean[16];

    //a, b가 연속으로 올때 겹치는 부분 제외 a영역 리턴
    public static String makeShortestString(String a, String b) {
        for (int i = 0; i <= a.length(); i++) {
            String tmpA = a.substring(i);
            boolean flag = true;
            for (int j = 0; j < tmpA.length(); j++) {
                //b의 길이를 넘어 설때
                if (j >= b.length() || tmpA.charAt(j) != b.charAt(j)) {
                    flag = false;
                    break;
                }
            }
            //문자열이 겹칠때
            if (flag) return i == 0 ? "" : a.substring(0, i);
        }
        return a;
    }

    //sString을 시작 문자열로하고 bitMask만큼 문자열만큼 남았을 때 최소 길이 문자열 출력
    public static String solve(int ssInd, int bitMask) {
        //기저 조건 -> 모든 문자를 다 썼을 때
        if (bitMask == 0) return subString[ssInd];
        if (!dp[ssInd][bitMask].equals("")) return dp[ssInd][bitMask];
        String minString = "";
        int minLength = Integer.MAX_VALUE;
        for (int i = 1; i <= K; i++) {
            if ((bitMask & (1<<i)) == 0) continue;
            if (erase[i]) continue;
            //i번째 문자열이 남아 있을 때
            String tmp = shortestString[ssInd][i] + solve(i, bitMask - (1<<i));
            if (minLength > tmp.length()) {
                minLength = tmp.length();
                minString = tmp;
            }
        }
        dp[ssInd][bitMask] = minString;
        return dp[ssInd][bitMask];
    }

    public static void clear() {
        for (int i = 0; i < 16; i++) {
            for (int j = 0; j < (1 << 16); j++) {
                dp[i][j] = "";
            }
            erase[i] = false;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        C = sc.nextInt();
        for (int c = 0; c < C; c++) {
            K = sc.nextInt();
            clear();
            subString[0] = "";
            for (int k = 1; k <= K; k++)
                subString[k] = sc.next();
            //특정 문자열에 포함되는 문자열 제거
            for (int i = 1; i <= K; i++) {
                if (erase[i]) continue;
                for (int j = 1; j <= K; j++) {
                    if (i == j) continue;
                    if (subString[i].contains(subString[j])) erase[j] = true;
                }
            }
            //a,b이어질때 겹치는 부분 제외 a영역 저장시켜줌
            for (int i = 0; i <= K; i++) {
                for (int j = 0; j <= K; j++) {
                    if (i == j) continue;
                    if (erase[i] || erase[j]) continue;
                    shortestString[i][j] = makeShortestString(subString[i], subString[j]);
                }
            }
            //실제 계산
            int tmpBitMask = (1<<(K+1)) - 2;
            for (int i = 1; i <= K; i++)
                if (erase[i]) tmpBitMask -= (1<<i);
            System.out.println(solve(0, tmpBitMask));
        }
    }
}