백준 15483번 최소 편집

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

Edit Distance 알고리즘 문제였습니다.

간단하게 설명하기 위해 문자열 DOG와 SOL로 설명하겠습니다.

	공백	D	O	G
공백	0	1	2	3
S	1	1	2	3
O	2	2	1	2
L	3	3	2	2

 SOL을 기준으로 다음 과정을 설명하자면 (공백을 0으로 표현)

i) 0

a) 0->0: (0)

b) 0->0D: D 삽입(1)

c) 0->0DO: DO 삽입(2)

d) 0->0DOG: DOG 삽입(3)

ii) 0S 

a) 0S->0: S 삭제(1)

b) 0S->0D: S->D 치환(1)

c) 0S->0DO: S->D 치환 + O 추가(2)

d) 0S->0DOG: S->D 치환 + OG 추가(3)

iii) 0SO 

a) 0SO->0: SO 삭제(2)

b) 0SO->0D: O 삭제+S->D 치환(2)

c) 0SO->ODO: S->D 치환(1)

d) 0SO->0DOG: S->D 치환 + G 추가(2)

iv) 0SOL

a) 0SOL->0: SOL 삭제(3)

b) 0SOL->0D: OL 삭제 + S->D 치환(3)

c) 0SOL->0DO: L 삭제+S->D 치환(2)

d) 0SOL->0DOG: L->G, S->D 치환(2)

따라서 0SOL->0DOG으로 치환하는데 최소 편집 횟수는 2이다.

#include <iostream>

#include <string>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 1000 + 1;

 

string S1, S2;

int cache[MAX][MAX];

 

void preCalculate(int length1, int length2)

{

        cache[0][0] = 0;

        //비어있는 문자열에서 편집 횟수

        for (int i = 1; i <= length2; i++)

                 cache[0][i] = i;

        for (int j = 1; j <= length1; j++)

                 cache[j][0] = j;

}

 

int minEdit(int length1, int length2)

{

        //기저 사례

        if (length1<0 && length2<0)

                 return 0;

 

        int &result = cache[length1][length2];

        if (result != -1)

                 return result;

       

        result = 0;

 

        if (S1[length1] == S2[length2]) //끝에 글자가 같다면

                 result = minEdit(length1 - 1, length2 - 1);

        else

                 //삽입, 삭제, 치환

                 result = 1 + min(minEdit(length1 - 1, length2), min(minEdit(length1, length2 - 1), minEdit(length1 - 1, length2 - 1)));

 

        return result;

}

 

int main(void)

{

        string temp1, temp2;

        cin >> temp1 >> temp2;

 

        //각 문자열 맨 앞 인덱스는 공문자

        S1 += " ";

        S1 += temp1;

        S2 += " ";

        S2 += temp2;

 

        int length1 = S1.size() - 1, length2 = S2.size() - 1;

 

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

        preCalculate(length1, length2);

 

        cout << minEdit(length1, length2) << endl;

        return 0;

}

 

개발환경:Visual Studio 2017

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