백준 15484번 최소 편집 2

문제 링크입니다: https://www.acmicpc.net/problem/15484

알고리즘 학회에서 Edit Distance 알고리즘을 배운 뒤 15483번 최소편집(http://jaimemin.tistory.com/540) 문제를 풀고 신이 나서 15484번 문제를 시도했었는데 보기 좋게 실패했었습니다.

그 당시에는 "Edit Distance 알고리즘에서 transpose만 추가된건데 어려울게 머가 있겠어?"라는 생각으로 시도를 했는데 생각만큼 만만한 문제가 아니였습니다.

위키피디아에서 검색해보니 Edit Distance + transpose 알고리즘은 Damerau-Levenshtein distance 알고리즘(https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance#Distance_with_adjacent_transpositions)이였고 수도코드를 봐도 복잡한 알고리즘이였습니다.

위키피디아와 같은 학교 학우님인 ssangba55님(https://blog.naver.com/pasdfq)의 도움(ssangba55님의 노력 99% + 위키피디아 링크 제공한 저의 1%) 덕분에 100%는 아니지만 Damerau-Levenshtein distance 알고리즘이 어느정도 이해가 되었습니다!

삽입, 삭제, 교체는 기존에 알고 있던 Edit Distance 알고리즘과 동일합니다.

여기서 추가된 transpose(교환)은 3단계에 걸쳐 이루어집니다.

matched[i][j][0]: j<X이면서 s1[i] == s2[X]인 최솟값 X

matched[i][j][1]: i<X이면서 s1[X] == s2[j]인 최솟값 X

matched[idx1][idx2][0] (==s1[idx1]) 을 X라고 하고, matched[idx1][idx2][1] (==s2[idx2]) 을 Y라고 합니다.

N . . . Y . . .

M . . X . . . .

1. s1[idx1]과 s1[Y] 사이를 전부 없애고 (비용: Y-idx1-1)

2. s1[idx1]과 s1[Y]를 교환하고 (비용: 1)

3. s2[idx2]와 s2[X] 사이에 있는 것을 삽입한다 (비용: X-idx2-1)

아래는 ssangba55님이 작성하신 코드입니다.

#include <iostream>

#include <string>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 1000;

 

string s1, s2;

int cache[MAX][MAX];

int matched[MAX][MAX][2];

 

//Damerau_Levenshtein(idx1, idx2)= s1[idx1:], s2[idx2:] 부터 가능한 최소 편집의 수

int Damerau_Levenshtein(int idx1, int idx2)

{

        //기저 사례(삭제 비용)

        if (idx1 == s1.size())

                 return s2.size() - idx2;

        if (idx2 == s2.size())

                 return s1.size() - idx1;

 

        int &result = cache[idx1][idx2];

        if (result != -1)

                 return result;

 

        //s1[n]에 s2[m]을 삽입한다

        result = 1 + Damerau_Levenshtein(idx1, idx2 + 1);

 

        //s1[n]을 삭제한다

        result = min(result, 1 + Damerau_Levenshtein(idx1 + 1, idx2));

 

        //s1[n]을 s2[m]으로 교체한다

        //단, s1[n] == s2[m]이면 그냥 지나친다

        result = min(result, (s1[idx1] != s2[idx2]) + Damerau_Levenshtein(idx1 + 1, idx2 + 1));

 

        //교환할 대상이 없으면 종료

        if (matched[idx1][idx2][0] == -1 || matched[idx1][idx2][1] == -1)

                 return result;

 

        /*

        matched[idx1][idx2][0] (==s1[idx1]) 을 X라고 하고

        matched[idx1][idx2][1] (==s2[idx2]) 을 Y라고 하면

        N...Y...

        M..X....

        1. s1[idx1]과 s1[Y] 사이를 전부 없애고 (비용: Y-idx1-1)

        2. s1[idx1]과 s1[Y]를 교환하고 (비용: 1)

        3. s2[idx2]와 s2[X] 사이에 있는 것을 삽입한다 (비용: X-idx2-1)

       

        이제 X+1, Y+1부터 다시 만들면 된다

        */

        int &X = matched[idx1][idx2][0];

        int &Y = matched[idx1][idx2][1];

 

        result = min(result, (Y - idx1 - 1) + 1 + (X - idx2 - 1) + Damerau_Levenshtein(Y + 1, X + 1));

        return result;

}

 

int main(void)

{

        cin >> s1 >> s2;

        memset(cache, -1, sizeof(cache));

        memset(matched, -1, sizeof(matched));

 

        //matched[i][j][0]: j<X이면서 s1[i] == s2[X]인 최솟값 X

        //matched[i][j][1]: i<X이면서 s1[X] == s2[j]인 최솟값 X

        int alphabet[26];

       

        memset(alphabet, -1, sizeof(alphabet));

        for (int j = s2.size() - 1; j >= 0; j--)

        {

                 for (int i = s1.size() - 1; i >= 0; i--)

                         matched[i][j][0] = alphabet[s1[i] - 'a'];

                 alphabet[s2[j] - 'a'] = j;

        }

 

        memset(alphabet, -1, sizeof(alphabet));

        for (int i = s1.size() - 1; i >= 0; i--)

        {

                 for (int j = s2.size() - 1; j >= 0; j--)

                         matched[i][j][1] = alphabet[s2[j] - 'a'];

                 alphabet[s1[i] - 'a'] = i;

        }

 

        cout << Damerau_Levenshtein(0, 0) << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~