[algospot] RESTORE

문제링크 입니다

비트마스크를 응용해서 문제를 많이 풀어봐야 할 것 같습니다….

[RESTORE] 문제 😂😂😂😂😂

토요일에 출근해서 연구실에서 놀고 있던 대학원생 진호는 실수로 실험에 사용하던 데이터를 삭제하고 말았습니다. 복사본도 없는 터라 이대로라면 교수님의 진노를 한 몸에 받을 것은 자명한 일, 따라서 진호는 그럴 듯해 보이는 데이터를 위조하여 교수님의 분노를 피해 가기로 합니다. 우리가 데이터에 대해 알고있는 것은, 데이터가 k개의 문자열 조각을 부분 문자열로 포함하며, 모두 알파벳 소문자로 구성된다는 사실 밖에 없습니다. (어떤 문자열의 부분 문자열은 해당 문자열의 연속된 일부분입니다.)

주어진 문자열 조각들을 모두 부분 문자열로 포함하는 문자열 중 가장 짧은 것을 계산하는 프로그램을 작성하세요. 만약 이와 같은 문자열이 여럿이라면 아무 문자열이나 출력하면 됩니다.

입력

입력의 첫 줄에는 테스트 케이스의 수 C(C≤50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 부분 문자열의 수 k(1≤k≤15)가 주어지고, 다음 k줄에 알파벳 소문자로만 구성된 문자열 조각이 주어집니다. 각 문자열 조각의 길이는 1 이상 40 이하입니다.

출력

각 테스트 케이스마다 한 줄로, 해당 문자열을 모두 포함하는 가장 짧은 문자열 중 하나를 출력합니다.

입력 예제

3
3
geo
oji
jing
2
world
hello
3
abrac
cadabra
dabr

출력 예제

geojing
helloworld
cadabrac

전체 코드는 다음과 같습니다.

//
//  RESTORE.cpp
//  AALGGO
//
//  Created by inhyeoK on 2021/10/13.
//
// 어떤 문자열 조각에도 포함되지 않는 문자를 더할 일은 절대 없다.
// 연속해서 출현하는 문자열들의 접미사와 접두사를 최대한 많이 겹치게 해야
// 가장 짧은 문자열을 찾을 수 있다.
// 한 문자열 조각이 다른 문자열에 포함될 경우 무시하면 된다.
// 전처리 과정에서 조각들을 입력받자마자 문자열 중 다른 문자열에 포함된 것이 있나 살피고 이들을 다 지워 버리도록 한다.
//

#include <iostream>
#include <cstring> // memset
#include <fstream>
#include <string> // string
#include <algorithm> // sort

using namespace std;

ifstream fin("RESTORE.txt");

const int MAX_N = 15;
int K;
string word[MAX_N];
int cache[MAX_N][1<<MAX_N] , overlap[MAX_N][MAX_N];

void preCalc(){
    for(int i=0; i<K; i++){
        for(int j=0; j<K; j++){
            for(int length = min(word[i].size(), word[j].size()); length>0; length-- ){
                if(word[i].substr(word[i].size()-length) == word[j].substr(0,length)){
                    overlap[i][j] = length;
                    break;
                }
            }
        }
    }
    return;
}

// last : 마지막에 출현한 조각
// used : 지금까지 출현한 조각 집합.
int restore(int last, int used){
    //기저 사례
    if(used == (1<<K)-1) return 0;
    //memoization
    int &ret = cache[last][used];
    if(ret!=-1) return ret;
    ret = 0;
    for(int next = 0; next < K ; next++)
        if((used & (1<<next)) == 0) {
            int cand = overlap[last][next] + restore(next, used + (1<<next));
            ret = max(ret,cand);
        }
    return ret;
}

string reconstruct(int last, int used){
    if(used==(1<<K)-1) return "";
    for(int next = 0; next < K ; next++){
        // next 가 이미 사용되었으면 패쓰
        if(used & (1<<next)) continue;
        // next를 사용했을 경우의 답이 최적해와 같다면 next 사용
        int ifUsed = overlap[last][next] + restore(next, used + (1<<next));
        if(restore(last,used) == ifUsed)
            return (word[next].substr(overlap[last][next]) + reconstruct(next, used + (1<<next)));
    }
    return "ERRORRORO";
}
int main(int argc, const char * argv[]) {
    int test_case;
    fin >> test_case;
    for(int i = 0; i < test_case; i++){
        fin >> K;
        memset(cache, -1, sizeof(cache));
        memset(overlap, 0, sizeof(overlap));
        for(int j=0; j<K; j++){
            fin >> word[j];
        }

        while (true)
       {
           bool removed = false;
           for(int j=0; j<K && !removed; j++)
              for(int k=0; k<K; k++)
                  if (j != k && word[j].find(word[k]) != -1) //부분문자열이 겹친다면 삭제
                  {
                      //heapSort 삭제와 비슷한 과정
                      word[k] = word[K - 1]; //맨 끝에 있는 string과 위치변경
                      K--;
                      removed = true;
                  }
           if (!removed)
              break;
       }
        word[K] = "";
        preCalc();
        cout << reconstruct(K,0) << endl;
    }

    return 0;
}