[Algospot] 실험 데이터 복구하기 (문제 ID : RESTORE)

문제

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

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

 

입력

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

 

출력

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

---

역시나 인간의 뇌로 생각하면 쉬운 문제지만 이를 코드로 옮기는 것은 매우 어렵다. 

 

문제는 여러 문자열의 조각이 들어올 때 문자열을 최대한 서로 겹쳐서 짧은 문자열을 출력하는 것이다. 

 

사전 작업으로 문자열이 다른 문자열에 완전히 포함되는 것은 제외한다. main 함수에서 wodr[i].find(word[j]) != -1 이 부분을 살펴보자. 

str.find 함수는 str속에 다른 문자열이 있는지 확인해 그 위치를 반환하는 함수이다. 따라서 그 반환값이 -1이 아니라는 것은 j번째 문자열이 i번째 문자열에 포함된다는 뜻이므로 해당 문자열을 제일 마지막 문자열로 교체하고 K를 1 줄이는 방식으로 j번째 문자열을 삭제한다.

 

그 후 overlap 함수와 over 배열을 통해 문자열이 서로 겹치는 최대 길이를 구한다. 이 길이를 이용해서 문자열을 조합하면 제일 짧은 문자열의 길이를 구할 수 있게 된다. overlap또한 사전작업으로 모두 마친 후 resotre 함수를 통해 최적해의 점수를 구한다. restore 함수는 외판원 순회 문제와 매우 비슷하다고 한다. 이미 방문한 문자열이면 넘어가고 방문하지 않은 문자열 중에 가장 많이 겹치는 문자열을 고르는 식이다.

 

최종적으로 reconstruct 함수를 통해 결과 문자열을 반환한다. 모든 문자열을 방문했으면 빈 문자열을 반환하고 방문하지 않은 문자열 중에 답이 최적해와 같다면 그 문자열을 포함한다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Algospot/RESTORE.cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int C, K;
const int MAX = 15;
string word[15];
int dp[15][1 << 15], over[15][15];

int restore(int last, int used)
{
	if (used == (1 << K) - 1) return 0;
	int& res = dp[last][used];
	if (res != -1) return res;
	res = 0;
	for (int i = 0; i < K; i++) {
		if ((used & (1 << i)) == 0) {
			int cand = over[last][i] + restore(i, used + (1 << i));
			res = max(res, cand);
		}
	}
	return res;
}
string reconstruct(int last, int used)
{
	if (used == (1 << K) - 1) return "";
	for (int next = 0; next < K; next++) {
		if (used & (1 << next)) continue;
		int ifUsed = restore(next, used + (1 << next)) + over[last][next];
		if (restore(last, used) == ifUsed) {
			return (word[next].substr(over[last][next]) + reconstruct(next, used + (1 << next)));
		}
	}
	return "error";
}
int overlap(string& s1, string& s2)
{
	for (int len = min(s1.size(), s2.size()); len > 0; len--) {
		if (s1.substr(s1.size() - len) == s2.substr(0, len)) {
			return len;
		}
	}
	return 0;
}
int main()
{
	cin >> C;
	while (C--) {
		cin >> K;;
		for (int i = 0; i < K; i++)
			cin >> word[i];
		memset(dp, -1, sizeof(dp));
		memset(over, -1, sizeof(over));
		while (true) {
			bool removed = false;
			for (int i = 0; i < K && !removed; i++) {
				for (int j = 0; j < K; j++) {
					if (i != j && word[i].find(word[j]) != -1) {
						word[j] = word[K-1];
						K--;
						removed = true;

					}
				}
			}
			if (!removed) break;
		}
		word[K] = "";

		for (int i = 0; i <= K; i++)
			for (int j = 0; j <= K; j++) 
				over[i][j] = overlap(word[i], word[j]);
		
		cout << reconstruct(K, 0) << endl;

	}
}