[종만북] 문제: RESTORE

문제

문자열 $k(1 \leq k \leq 15)$개를 입력을 받아서, 해당 문자열을 한 줄로 모두 포함하는 가장 짧은 문자열 하나를 출력합니다.

$length(k):1 \leq k \leq 40$

문제 링크

---

서론

이번에는 입력이 문자열 여러 개인 경우에 대해서 Dynamic programming을 적용해보려고 합니다.

---

알고리즘 구상

문제 단순화 하기

문자열 두 개가 있다고 가정해봅시다. 문자열 두 개의 관계는 크게 2가지 경우로 나눌 수 있습니다.

1. 문자열이 다른 문자열에 완전히 포함됩니다.
2. 문자열간 겹치는 부분이 존재합니다.

첫 번째 경우는 구할 필요가 없죠. 따라서 이를 배제합시다.

두 번째 경우가 중요한데, 이 겹치는 부분을 최대화하면 됩니다!

점화식으로 나타내보기

단어 a 뒤에 단어 b가 등장 시 최대 겹치는 부분을 계산해주는 함수 $overlap(a, b)$를 구현합니다.

이 $overlap$을 최대화하면 되겠죠!

DP를 어떻게 적용하지

처음에는 문자열 k개를 배치하는 경우를 모든 저장하는 방법으로 구현하려 했으나. 조금 생각해보면, 말이 안되는 이야기죠, 총 $k!$개의 경우의 수가 존재하는데, 문자열이 전부 서로 다르다고 하면, $15!$는 너무 큰 숫자죠.. 이런 식으로는 DP를 구현할 수 없습니다.

따라서 최적 값의 순열을 찾는 문제에 DP를 적용하려면, bool[]을 쓰면 됩니다!

입력 값의 개수가 32개를 넘지 않는다면, 이를 bitmask형태로 나타낼 수도 있겠죠. 왜냐하면 나올 수 있는 경우의 수는 $2^{32}$니까요!

Subproblem과 점화식 정의

마지막에 사용한 단어 last, 지금까지 사용한 단어들 used을 이용해서 Subproblem을 정의할 수 있죠. 이 Subproblem을 이용해 점화식을 정의할 수 있습니다.

점화식: \(restore(last, used) = \max_{next \in used^\complement} (overlap(last, next) + restore(next, used \bigcup \{next\}))\)

알고리즘 순서

1. 포함되는 문자열을 없앱니다.
2. $restore$를 이용해 DP table을 얻습니다.
3. DP table을 이용해 값을 traceback합니다.

---

알고리즘 구현

전처리 함수

먼저 문자열간에 포함되는 문자열을 모두 없애야 겠죠, 구현하는 방법은 여러 가지가 있겠으나, std::string::find()를 이용해봅시다!

std::string::find()는 문자열에서 부분 문자열이 어느 index에 존재하는지 조사하는 함수입니다. 만약 존재하지 않으면, std::string::npos라는 특별한 상수 값을 반환합니다.

이를 이용해서 존재 유무를 찾는 bool를 작성합시다.

bool IsExistAinB = result[j].find(input[i]) != string::npos;

이런 식으로 작성할 수 있습니다.

이를 이용해서 전처리 함수인 void removeSubstrings()를 구현합니다.

void removeSubstrings() {
    sort(input.begin(), input.end(),
         [&](const string &a, const string &b) -> bool {
             return a.size() > b.size();
         });

    vector<string> result;

    for (int i = 0; i < input.size(); ++i) {
        bool isSub = false;
        for (int j = 0; j < result.size(); ++j) {
            if (result[j].find(input[i]) != string::npos) {
                isSub = true;
                break;
            }
        }
        if (!isSub) {
            result.push_back(input[i]);
        }
    }
    input = std::move(result); // result도 초기화됩니다.
    k = input.size();

} // 포함 관계에 있는 원소를 없앱니다.

$overlap(a, b)$를 전부 구해주는 함수 calOverlap()도 작성합니다!

int overlap[15][15];
void calOverlap() {
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < k; j++) {
            overlap[i][j] = 0;
            for (int L = min(input[i].size(), input[j].size()); L >= 1; --L) {
                if (input[i].substr(input[i].size() - L, L) ==
                    input[j].substr(0, L)) {
                    overlap[i][j] = L;
                    break;
                }
            }
        }
    }
} // overlap[][]을 미리 구합니다.

$restore(last, used)$

int DP[15][1 << 15];
int restore(int last, int used) {
    if (used == (1 << k) - 1) return 0; // base case

    int &ret = DP[last][used];
    if (ret != -1) return ret; // 메모이제이션

    ret = 0;
    for (int i = 0; i < k; i++) {
        if (used & (1 << i)) continue;
        int cand = overlap[last][i] + restore(i, used | (1 << i));
        ret = max(ret, cand);
    }
    return ret; // recursive case
}

전 원소인 last와 bitmask를 적용한 bool[] -> int used 파라미터를 이용해서 restore(last, used)를 구현합니다!

$traceback(last, used)$

string traceback(int last, int used) {
    if (used == (1 << k) - 1) return "";

    for (int i = 0; i < k; i++) {
        if (used & (1 << i)) continue;
        int ifUsed = restore(i, used + (1 << i)) + overlap[last][i];
        if (restore(last, used) == ifUsed)
            return (input[i].substr(overlap[last][i]) +
                    traceback(i, used | (1 << i)));
    }
    return "???";
}

restore()를 이용해 traceback()를 구현합니다.

최종 코드

여기에서 확인하세요!