[알고스팟] 실험 데이터 복구하기

RESTORE <- 클릭시 문제 링크로 이동합니다.

실험 데이터 복구하기

• 문제
• 답안 제출
• 통계

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • RESTORE
  • 2000ms
  • 65536kb
  • 1726
  • 380 (22%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 연습문제
  • 보기

문제

토요일에 출근해서 연구실에서 놀고 있던 대학원생 진호는 실수로 실험에 사용하던 데이터를 삭제하고 말았습니다. 복사본도 없는 터라 이대로라면 교수님의 진노를 한 몸에 받을 것은 자명한 일, 따라서 진호는 그럴 듯해 보이는 데이터를 위조하여 교수님의 분노를 피해 가기로 합니다. 우리가 데이터에 대해 알고있는 것은, 데이터가 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

어떻게 풀까?

뭔가 문제 풀이를 어떻게 설명해드려야될지 정말 고민되는 문제였습니다!

이 문제를 풀다보면 몇가지 규칙이 보입니다.

1. 아예 포함되는 문자는 삭제해도 무방하다.

2. 아예 겹치는 것이 없는 문자는 어떻게 끼워넣어도 상관없다.

3. 겹치는 문자를 최대로 해야지 가장 짧아진다!

이 정도만 만족하면 문제가 해결되는 것을 볼 수 있습니다!

가장 짧은 문자열 길이는 어떻게 찾는것이 좋을까요?

예제 1번을 예로 들겠습니다.

geo
oji
jing

우선 문자열이 겹치는 것을 생각하지 않고 k개의 문자열의 순서를 나열해 봅시다.

geo oji jing

geo jing oji

등이 나올 것입니다.

그럼 이제 해줘야 할 일은 3번을 이용해서 겹치는 부분을 최대화 하는 것이 될겁니다.

geo oji jing의 경우에는 geojing가 되겠죠!

이렇게 하면 문제의 답을 꽤 쉽게 찾을 수 있게 됩니다.

어떻게 문자열 순서를 하던 결국 총 길이는 같아질 것입니다!

달라지는 곳은 바로 i - 1과 i번째의 단어가 얼마나 겹치느냐의 차이이죠!

즉, 이 문제는 가장 겹치는 부분이 많은 수열의 순서를 찾아내는 것이 됩니다!

이렇게 되면 살짝 문제가 생기는 부분이 있습니다.

바로 1번에서 말했던, 아예 포함되는 부분을 삭제해야한다는 것이죠.

예를 들어보겠습니다!

abcdef - de - cdefgh를 겹친다고 생각해봅시다!

이렇게 되면, 실제로는 abcdefgh가 정답이 되지만,

지금 적용하려는 알고리즘에 의하면 i - 2를 보지 않기 때문에 abcdef와 cdefgh가 abcdefgh로 겹쳐질 수 있다는 사실을 보기 힘들게 되죠.

즉, 포함되는 문자열이 있다면 바로 삭제 하는게 좋다는 것입니다!

이제 중복되는 부분이 어떻게 되는지 생각해봅시다.

문자열이 10개가 주어졌다고 생각해봅시다.

그리고, 현재 0번 문자열 - 1번 문자열 - 2번 문자열을 방문한 상태입니다.

그럼 이제 나머지 3,4,5,6,7,8,9번 문자열에서 만들 수 있는 가장 짧은 문자열을 만드는 것이 현재 상태에서 가장 짧은 문자열을 만드는 방법입니다!

다음으로, 1번 문자열 - 0번 문자열 - 2번 문자열을 방문한 상태라고 합시다.

위에서 했던 것처럼 또다시 3,4,5,6,7,8,9번 문자열에서 만들 수 있는 가장 짧은 문자열을 만드는 것이 현재 상태에서 가장 짧은 문자열을 만드는 방법입니다!

즉, 현재 방문한 위치들을 true와 false를 통해 k자리수의 2진법 수로 나타낸다면 비트마스킹을 통해서 중복 문제를 해결할 수 있을 것 입니다!

다만, 첫번째로 선택된 글자에 따라서 앞의 글자와 겹치는 글자가 달라지기 때문에, 선택된 인덱스도 포함해서 메모이제이션을 적용합시다!

이제 지금까지 생각했던 것을 토대로 점화식을 만들어봅시다!

restore는 총 겹져있는 글자수를 반환하고, operlap(a,b)는 a 문자열과 b 문자열이 실제로 겹치는 문자의 수라고 입니다.

다만, 이 문제는 실제로 가장 짧은 글자를 출력하는 것이 목표이기 때문에 여기서 끝나지 않습니다.

저 같은 경우에는 마찬가지로 selected와 used를 통해서 가장 겹쳐져 있는 글자수가 많은 next값이 온다면,

해당 next를 path[selected][used]에 저장했습니다.

그림으로 보면 다음과 같은 알고리즘이라고 할 수 있겠습니다.

처음에는 geo는 jing로 가야한다고 합니다.

하지만 oji가 겹치는 곳이 알고보니 더 많았고, geo는 oji로 가야한다고 수정합니다.

또한, 출력할때도 문자열을 그대로 출력하면 예제 1번의 경우에는 geoojijing가 출력되겠죠??

하지만, operlap이 얼마인지 이미 알기 때문에 그 문제도 해결할 수 있습니다!

geo와 oji가 겹치는게 1이기 때문에 1번 문자는 ge만 출력하면 됩니다! 왜냐하면 다음거에서 어짜피 나머지 1개를 출력해주기 때문이죠!

이러한 방법들을 어떻게 코드로 구현했는지 알아봅시다.

코드

#pragma once
#include<cstdio>
#include<cstring>
 
int n;
char str[16][41], res[1000], tstr[16][41];
int mlen[16][1 << 15], len[16], tlen[16], order[16], temp[16];
int to[16][16], path[16][1 << 15];
 
int min(int i1, int i2)
{
    return i1 < i2 ? i1 : i2;
}
 
int getLen(int idx, int visit)
{
    if (visit == (1 << n) - 1)
    {
        path[idx][visit] = 0;
        return 0;
    }
 
    int &ret = mlen[idx][visit];
    if (ret != -1) return ret;
 
    ret = 987654321;
 
    for (int next = 0; next < n; next++)
    {
        if ((1 << next) & visit) continue; //이미 방문한 인덱스
 
        int dist = getLen(next + 1, visit | (1 << next)) - to[idx][next + 1] + len[next + 1];
        
        if (dist < ret)
        {
            path[idx][visit] = next + 1;
            ret = dist;
        }
    }
 
    return ret;
}
 
//길이가 긴 순서대로 merge
void mergeSort(int left, int m, int right)
{
    int l = left, r = m + 1, k = l;
 
    while (l <= m && r <= right)
    {
        if (len[l] < len[r])
        {
            tlen[k] = len[r];
            temp[k++] = order[r++];
        }
        else
        {
            tlen[k] = len[l];
            temp[k++] = order[l++];
        }
    }
 
    while (l <= m) {
        tlen[k] = len[l];
        temp[k++] = order[l++];
    }
 
    while (r <= right) {
        tlen[k] = len[r];
        temp[k++] = order[r++];
    }
 
    for (int i = left; i <= right; i++) {
        len[i] = tlen[i];
        order[i] = temp[i];
    }
}
 
void merge(int l, int r) {
    if (l < r) {
        int m = (l + r) / 2;
        merge(l, m);
        merge(m + 1, r);
        mergeSort(l, m, r);
    }
}
 
//경로 탐색 만약 경로면 다음 문자열과 겹치기 전 부분까지만 출력!
void setRes(int idx, int visit, int &l)
{
    int next = path[idx][visit];
 
    for (int i = 0; i < len[idx] - to[idx][next]; i++)
    {
        res[l++] = str[idx][i];
    }
    if(visit != (1 << n) - 1) setRes(next, visit | (1 << (next - 1)), l);
}
 
void init()
{
    //포함되는지 검사
    for (int i = 1; i <= n; i++)
    {
        for (int j = i + 1; j <= n;)
        {
            bool part = false;
            for (int k = 0; k <= len[i] - len[j]; k++)
            {
                bool same = true;
                for (int l = 0; l < len[j]; l++)
                {
                    if (str[i][k + l] != str[j][l])
                    {
                        same = false; 
                        break;
                    }
                }
                if (same)
                {
                    part = true;
                    break;
                }
            }
 
            //포함된다면 해당 문자열 삭제
            if (part)
            {
                for (int k = j; k < n; k++)
                {
                    memcpy(str[k], str[k + 1], sizeof(str[k]));
                    len[k] = len[k + 1];
                }
                n--;
            }
            else
            {
                j++;
            }
        }
    }
 
    memset(to, 0, sizeof(to));
    memset(mlen, -1, sizeof(mlen));
    memset(path, 0, sizeof(path));
 
    //겹치는 길이 검사
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i == j) continue;
            int st = 0 > len[i] - len[j] + 1 ? 0 : len[i] - len[j] + 1;
            
            int k;
            for (k = st; k < len[i]; k++)
            {
                bool allsame = true;
                for (int l = 0; k + l < len[i]; l++)
                {
                    if (str[i][k + l] != str[j][l])
                    {
                        allsame = false;
                        break;
                    }
                }
                if (allsame)
                {
                    break;
                }
            }
 
            to[i][j] = len[i] - k;
        }
    }
}
 
int main()
{
    int tc;
    scanf("%d\n", &tc);
 
    while (tc--)
    {
 
        scanf("%d\n", &n);
        for (int i = 1; i <= n; i++)
        {
            order[i] = i;
            scanf("%s\n", str[i]);
            len[i] = strlen(str[i]);
        }
 
        merge(1, n);
 
        for (int i = 1; i <= n; i++)
        {
            memcpy(tstr[i], str[order[i]], sizeof(tstr[i]));
        }
 
        memcpy(str, tstr, sizeof(str));
        
        init();
        int idx = getLen(0, 0);
        int l = 0;
        setRes(0, 0, l);
        res[l] = 0;
 
        printf("%s\n", res);
    }
    return 0;
}

여담

정말 어려웠습니다!

뭔가 알고리즘은 금방 찾았지만

1번 조건에 포함되면 삭제한다는 부분에서 삽질을 많이했네요!

처음에 문자열의 길이가 큰 것을 앞으로 오도록하니 문제가 훨씬 쉽게 풀렸습니다!

시간복잡도는 어떻게 될까요?

부분문제가 k * 2^k이고, 함수 내에서 k번의 반복을 하기 때문에 의 시간복잡도를 가지게 됩니당!!!