[RESTORE] 실험 데이터 복구하기 문제

  • robustFlame
    robustFlame

    문제 링크

    질문 요약

    • 문제의 오답을 유도하는 케이스를 찾지 못하고 있습니다.
    • 또는 코드의 논리적 오류를 찾지 못하고 있습니다.

    문제 해결 방향

    1. 문자열 a뒤에 문자열 b를 겹쳐서 놓을 때, 가정 적은 길이를 추가하여 붙일 수 있는 길이(즉, 가장 많은 부분이 겹칠 수 있는 길이를 찾는 것과 같습니다)를 전처리 과정으로 찾아놓는다.
    2. 가장 적은 길이의 문자열 조합을 찾는 완전 탐색 알고리즘을 작성한다.
    3. 2를 이용하여 최적의 답을 구성한다.

    JMBOOK에 있는 풀이 전략과 거의 유사합니다. 다만 모든 문자열의 조합을 완전 탐색으로 찾을 시, 모든 문자열의 조합 길이가 가장 작도록 해서 답을 유도한다는 점과 책에서는 시작 문자열을 별도로 지정해서 답을 찾도록 했지만 여기서는 -1 인덱스를 사용하여 첫 문자열을 찾는 것도 재귀 함수에 다 포함시켜놨습니다.

    제출 코드(오답)

    #include <bits/stdc++.h>
    using namespace std;
    
    int k;
    const int INF = 987654321;
    const int MAX_K = 15;
    // 문자열 조각들
    vector<string> substrings;  
    // appendLength[i][j] : substrings[i] 문자열 뒤에 substrings[j] 문자열이 올 때,
    // substrings[j]에서 겹치는 부분(접두사)을 제외한 길이, 즉 붙일 경우 추가할 길이
    int appendLength[MAX_K][MAX_K]; 
    // 메모이제이션
    int cache[MAX_K + 1][1 << MAX_K];
    // 문자열 조각 목록에 s를 추가한다.
    // 만약 다른 문자열에 부분 문자열로 속한다면 추가하지 않는다.
    // 만약 기존에 있는 문자열 조각을 부분 문자열로 포함한다면 그 문자열을 대체한다.
    void appendAtSubstrings(const string& s) {
        for (int i = 0; i < substrings.size(); i++) {
            if (substrings[i].length() >= s.length()) {
                // 기존 문자열에 부분 문자열인 경우 -> 종료
                if (substrings[i].find(s) != string::npos) 
                    return;
            }
            else {
                // 기존 문자열을 부분 문자열로 포함하는 경우 -> 대체 후 종료
                if (s.find(substrings[i]) != string::npos) {
                    substrings[i] = s;
                    return;
                }
            }
        }
        substrings.push_back(s);
    }
    // appendLength[a][b]를 설정한다.
    void setAppendLength(int a, int b) {
        if (a == b) return;
        const string& s1(substrings[a]);
        const string& s2(substrings[b]);
        int n1 = s1.length(), n2 = s2.length();
        // 최대 추가 길이는 s2 문자열 전체의 길이
        appendLength[a][b] = n2;
        int start = n1 <= n2 ? 1 : n1 - n2;
        for (int i = start; i < n1; i++) { 
            // s1문자열의 접미사와 s2문자열의 접두사 같으면 이 길이만큼 겹친다.
            // 가장 길이가 큰 문자열들부터 비교하므로 가장 먼저 이 조건이 성립되는 상황이
            // 가장 적은 appendLength[a][b]를 갖는다.
            if (s1.substr(i, n1 - i) == s2.substr(0, n1 - i)) {
               appendLength[a][b] = n2 - n1 + i;
               break;
            }
        }
    }
    // 현재까지 선택된 문자열들(picked)과 이전 문자열(last)이 주어질 때, 
    // 앞으로 남은 문자열을 겹쳐 만들 수 있는 문자열 길이 중 가장 짧은 길이를 반환한다. 
    int minLength(int last, int picked) {
        // 기저 사례: 모든 문자열을 다 선택한 경우
        if (picked == (1 << k) - 1) 
            return 0;
        // 메모이제이션
        int& ret = cache[last + 1][picked];
        if (ret != -1) return ret;
        ret = INF;
        // 아직 선택되지 않은 문자열에 대해서 모두 시도해본다.
        for (int next = 0; next < k; next++) {
            if ((picked & (1 << next)) == 0) {
                int nextPicked = picked | (1 << next);
                // -1이면 다음 문자열이 첫 문자열이므로 문자열 전체 길이만큼 추가된다.
                int appendLen = last == -1 ? substrings[next].length() : appendLength[last][next];
                ret = min(ret, appendLen + minLength(next, nextPicked));
            }
        }
        return ret;
    }
    // 가장 짧은 문자열을 갖도록 답을 만들어나간다.
    void constructAnswer(int last, int picked, string& answer) {
        // 기저 사례: 모든 문자열을 다 사용한 경우
        if (picked == (1 << k) - 1)
            return;
        for (int next = 0; next < k; next++) {
            // 아직 선택되지 않았고
            if ((picked & (1 << next)) == 0) {
                int optimal = minLength(last, picked);
                int nextPicked = picked | (1 << next);
                int appendLen = last == -1 ? substrings[next].length() : appendLength[last][next];
                int cand = appendLen + minLength(next, nextPicked);
                // next를 선택했을때 최적의 상황을 유지한다면 next 문자열을 다음 문자열로 선택한다.
                if (optimal == cand) {
                    int n = substrings[next].length();
                    // substrings[next]중 겹치지 않는 부분을 붙이고 재귀적으로 처리한다.
                    answer += substrings[next].substr(n - appendLen, appendLen);
                    constructAnswer(next, picked | (1 << next), answer);
                    break;
                }
            }
        }
    }
    
    int main() {
        ios::sync_with_stdio(false);
        int c;
        cin >> c;
        while (c--) {
            // 문자열들, appendLength, cache 초기화
            substrings.clear();
            memset(appendLength, 0, sizeof(appendLength));
            memset(cache, -1, sizeof(cache));
            cin >> k;
            // 문자열들을 받는다.
            for (int i = 0; i < k; i++) {
                string s;
                cin >> s;
                appendAtSubstrings(s);
            }
            // 문자열 개수를 재조정한다.
            k = substrings.size();
            // 각 문자열에 대해 appendLength() 설정한다.
            for (int i = 0; i < k; i++) {
                for (int j = i + 1; j < k; j++) {
                    setAppendLength(i, j);
                    setAppendLength(j, i);
                }
            }
            // 최적의 답을 구한다.
            string answer;
            constructAnswer(-1, 0, answer);
            cout << answer << '\n';
        }
    }
    

    8년 전
2개의 댓글이 있습니다.
  • JongMan
    JongMan

    a b abc 넣어보세요~


    8년 전 link
  • robustFlame
    robustFlame

    ㄴ감사합니다^^ 문자열 조각 목록 다듬는 전처리 과정을 너무 간단하게 생각했었네요;;


    8년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.