문제 : https://algospot.com/judge/problem/read/RESTORE
알고리즘 문제 해결 전략 1권 p.329
[알고리즘 STEP. 1]
결국 주어진 문자열 조각들을 모두 조합해서 이어보면서 총 길이가 최소가 되는 (= 겹치는 부분이 최대가 되는) 문자열을 출력하면 된다.
이는 외판원문제 (http://int-num.tistory.com/18)와 거의 똑같은 알고리즘이다. 거리 합의 최소를 반환하던걸 (겹치는)길이 합의 최대를 반환하도록 바꾸기만 하면 된다.
먼저 주어진 문자열 조각들의 겹치는 부분들의 길이를 먼저 구해서 행렬에 저장한다.
*int calcCommon(int i , int j)
i번째 문자열 뒤에 j번째 문자열을 붙일 때, 겹치는 길이를 반환한다.
1) i번째 문자열이 j번째 문자열 보다 길다면? 예를들어, [i 문자열] saoji [j 문자열] jing 이라하자.
이 때는 i문자열의 마지막 끝에 j문자열의 마지막 끝을 맞춘 상태로 시작해서
j를 하나씩 오른쪽으로 옮기며 겹치는 길이를 하나씩 줄여가며 최대 몇개의 문자를 겹칠 수 있는지 구한다.
1) j번째 문자열이 i번째 문자열 보다 길다면? 예를들어, [i 문자열] oji [j 문자열] jing 이라하자.
이 때는 j문자열의 처음부분에 i문자열을 맞춘 상태로 시작해서
j를 하나씩 오른쪽으로 옮기며 겹치는 길이를 하나씩 줄여가며 최대 몇개의 문자를 겹칠 수 있는지 구한다.
*int calcCommon(int i , int j)
모든 i, j에 대해 string i 뒤에 string j를 이어 붙일 때의 겹치는 길이를 구해서 commonLength[i][j]에 저장한다.
int calcCommon(int i , int j)
{
for(int common = min(piece[j].length(),piece[i].length()); common >0; common--){
FOR(index, common){
if(piece[i][piece[i].length()-common+index] != piece[j][index]) break;
if(index == common-1) return common;
}
}
return 0;
}
void precalc(){
//string i 뒤에 string j를 이어붙일 때 겹치는 길이
FOR(i, k){
FOR(j, k){
if(i==j) continue;
else commonLength[i][j] = calcCommon(i, j);
}
} } |
이제 이 commonLength 행렬을 가지고 외판원 문제를 풀 듯 문제를 풀면 된다.
다음과 같이 알고리즘을 짜면, 주어진 문자열을 이어붙일때 겹칠 수 있는 최대 길이가 출력된다.
//https://algospot.com/judge/problem/read/RESTORE
#include <iostream>
#include <vector>
#include <cstring>
#include <limits>
#define FOR(i, ed) for(int i = 0 ; i < ed; i++)
#define MINF std::numeric_limits<int>::min(); //*
using namespace std;
// input
int tc, k;
vector<string> piece;
//algorithm
int commonLength[16][16];
int cache[16][1<<16]; //j상태일 때 i에서부터 얻을수 있는 최대
int calcCommon(int i , int j){
for(int common = min(piece[j].length(),piece[i].length()); common >0; common--){
FOR(index, common){
if(piece[i][piece[i].length()-common+index] != piece[j][index]) break;
if(index == common-1) return common;
}
}
return 0;
}
void precalc(){
//string i 뒤에 string j를 이어붙일 때 겹치는 길이
FOR(i, k){
FOR(j, k){
if(i==j) continue;
else commonLength[i][j] = calcCommon(i, j);
}
}
}
int play(int here, int visited){
if(visited == (1<<k)-1) return 0;
int &ret = cache[here][visited];
if(ret >0) return ret;
ret = MINF;
FOR(next, k){
if(visited & (1<<next)) continue;
ret = max(ret, commonLength[here][next]+play(next, visited+(1<<next))); // *
}
return ret;
}
int main(){
// freopen("input.txt", "r", stdin);
cin >> tc;
while(tc--){
piece.clear();
memset(commonLength, 0, sizeof(commonLength));
memset(cache, -1, sizeof(cache));
cin >> k;
FOR(i, k){
string temp;
cin >> temp;
piece.push_back(temp);
}
cleansubstr();
// print(piece);
precalc();
// printcommonLength();
int rslt = MINF;
int start;
FOR(i, k){
int temp = play(i, 1<<i);
if(rslt <= temp){
rslt = temp;
start = i;
}
}
cout << play(start, 1<<start) << endl;
}
}
|
[알고리즘 STEP. 2]
문제에서 출력하고자 하는건 문자열 길이가 아니라 문자열 그 자체이다. 따라서 위에서 채워진 cache배열을 바탕으로 문자열을 재구성해야 한다.
현재 문자열과 지금까지 사용한 문자열들의 집합이 주어질 때,
앞으로 겹칠 수 있는 길이의 최댓값 = 남은 문자열 중 i문자열을 이었을 때의 겹치는 길이 + i문자열부터 나머지를 이용해서 만드는 문자열들의 겹치는 길이
라면 다음 선택은 i문자열 이라는 것을 알 수 있다.
이를 이용해서 문자열을 재구성 하는 함수는 다음과 같다.
string reconstruct(int here, int visited){
if(visited == (1<<k)-1) return "";
FOR(next, k){
if(visited & (1<<next)) continue;
int ifUsed = commonLength[here][next]+play(next, visited+(1<<next));
if(play(here, visited) == ifUsed){
// cout << next << endl;
return piece[next].substr(commonLength[here][next])+reconstruct(next, visited+(1<<next));
}
}
return "**";
} |
[알고리즘 STEP. 3]
이제 다 좋은데, 3번째 테스트케이스처럼 어떤 문자열이 다른 문자열에 완전히 속하는 경우에는 아예 없는 샘 쳐줘야 한다. (어차피 흡수되서 없어질거니깐..)
그래서 다른 문자열에 완전히 속하는 문자열은 아예 삭제해주는 코드를 작성했다.
void cleansubstr(){
int erase = 0;
for(int i = 1; i<k; i++){
FOR(j, i){
if(piece[j].find(piece[i]) != string::npos){
piece.erase(piece.begin()+i);
i--; k--;
break;
}else if(piece[i].find(piece[j]) != string::npos){
piece.erase(piece.begin()+j);
i--;j--;k--;
}
}
}
} |
[최종코드]
//https://algospot.com/judge/problem/read/RESTORE
#include <iostream>
#include <vector>
#include <cstring>
#include <limits>
#define FOR(i, ed) for(int i = 0 ; i < ed; i++)
#define MINF std::numeric_limits<int>::min(); //*
using namespace std;
// input
int tc, k;
vector<string> piece;
//algorithm
int commonLength[16][16];
int cache[16][1<<16]; //j상태일 때 i에서부터 얻을수 있는 최대
void printcommonLength(){
FOR(i, k) {
FOR(j, k)
cout << commonLength[i][j] << " ";
cout << endl;
}
}
void print(vector<string> &a) {
for (string x : a) {
cout << x << ' ';
}
cout << '\n';
}
void cleansubstr(){
int erase = 0;
for(int i = 1; i<k; i++){
FOR(j, i){
if(piece[j].find(piece[i]) != string::npos){
piece.erase(piece.begin()+i);
i--;
k--;
break;
}else if(piece[i].find(piece[j]) != string::npos){
piece.erase(piece.begin()+j);
i--;
j--;
k--;
}
}
}
}
int calcCommon(int i , int j){
for(int common = min(piece[j].length(),piece[i].length()); common >0; common--){
FOR(index, common){
if(piece[i][piece[i].length()-common+index] != piece[j][index]) break;
if(index == common-1) return common;
}
}
return 0;
}
void precalc(){
//string i 뒤에 string j를 이어붙일 때 겹치는 길이
FOR(i, k){
FOR(j, k){
if(i==j) continue;
else commonLength[i][j] = calcCommon(i, j);
}
}
}
int play(int here, int visited){
if(visited == (1<<k)-1) return 0;
int &ret = cache[here][visited];
if(ret >0) return ret;
ret = MINF;
FOR(next, k){
if(visited & (1<<next)) continue;
ret = max(ret, commonLength[here][next]+play(next, visited+(1<<next))); // *
}
return ret;
}
string reconstruct(int here, int visited){
if(visited == (1<<k)-1) return "";
FOR(next, k){
if(visited & (1<<next)) continue;
int ifUsed = commonLength[here][next]+play(next, visited+(1<<next));
if(play(here, visited) == ifUsed){
// cout << next << endl;
return piece[next].substr(commonLength[here][next])+reconstruct(next, visited+(1<<next));
}
}
return "**";
}
int main(){
// freopen("input.txt", "r", stdin);
cin >> tc;
while(tc--){
piece.clear();
memset(commonLength, 0, sizeof(commonLength));
memset(cache, -1, sizeof(cache));
cin >> k;
FOR(i, k){
string temp;
cin >> temp;
piece.push_back(temp);
}
cleansubstr();
// print(piece);
precalc();
// printcommonLength();
int rslt = MINF;
int start;
FOR(i, k){
int temp = play(i, 1<<i);
if(rslt <= temp){
rslt = temp;
start = i;
}
}
// cout << play(start, 1<<start) << endl;
cout << piece[start]+reconstruct(start, 1<<start) << endl;
}
}
|
[내가 헤맨 부분]
- 외판원문제랑 거의 똑같아서 앞부분까지 잘 했는데, 다른 문자열에 포함되는 문자열을 삭제하는 부분에서 인덱스를 제대로 안빼줘서 계속 오답이 나왔다.
무슨 생각을 했었는지
if(piece[j].find(piece[i]) != string::npos) 에서는 i--만 하고,
else if(piece[i].find(piece[j]) != string::npos)에서는 j--만 해줬다..
아마 break문으로 반복문 빠져나가니깐 상관 없다고 생각했었나 보다.....
void cleansubstr(){
int erase = 0;
for(int i = 1; i<k; i++){
FOR(j, i){
if(piece[j].find(piece[i]) != string::npos){
piece.erase(piece.begin()+i);
i--; k--;
break;
}else if(piece[i].find(piece[j]) != string::npos){
piece.erase(piece.begin()+j);
i--;j--;k--;
}
}
}
}
|