[AJ/DP] 두 문자열 사이의 거리

두 문자열 사이의 거리

문제

두 문자열 A, B 가 주어질 때, 두 문자열 사이의 거리를 구하려 한다. 여기서 거리는 다음과 같이 정의된다. 문자열 A가 주어질 때, 여기서 하나의 연산은 하나의 알파벳을 삽입 또는 삭제하는 것을 의미한다. 문자열 A와 B 사이의 거리란, A에서 시작하여 B를 만들기 위한 최소 연산의 횟수로 정의된다. 예를 들어, 문자열 A가 “abcabcd”이고, 문자열 B가 “abccabc” 라면, 문자열 A와 B 사이의 거리는 2가 된다. 왜냐하면 문자열 A의 세 번째에 ‘c’를 삽입하고, 가장 마지막에 있는 ‘d’를 삭제하면 문자열 B를 얻기 때문이다. 두 문자열이 주어질 때, 두 문자열 사이의 거리를 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄과 두 번째 줄에 문자열이 주어지며, 이 문자열의 길이는 1000을 넘지 않는다. 주어진 문자열은 대소문자가 섞여있다.  

출력

두 문자열 사이의 거리를 출력한다. (대문자 'A'와 소문자 'a'는 다른 문자로 취급한다.)

예제 입력

abcabcd

abccabc

예제 출력

2

---

풀이

위와 같이 두 문자열 간의 유사도를 알아내는 알고리즘을 '편집 거리 알고리즘'이라고 한다.

  - 삽입, 삭제, 대체 연산을 한다.

  - 두 데이터 사이의 유사도를 구할 때 사용되고 프로그램의 표절 여부, 철자 오류 검사 등에 사용할 수 있다. 예를 들어      자연어 번역, 유전자 유사도 등에 사용된다.

  - 편집거리 알고리즘은 다음과 같다.

   1. 비교하는 문자가 같을 경우 대각선 (i-1,j-1)의 값을 가지고

   2. 비교하는 문자가 다를 경우 대각선 (i-1, j-1) 과 좌측(i,j-1) 위 (i-1.j) 중 최소 값에 +1 한 값을 갖는다.

      - 대체 : 왼쪽 대각선+1, 추가 : 왼쪽+1 , 삭제 : 위쪽+1 이 된다.

 

* 의문점

1. 편집거리 알고리즘은 위와 같이 동작한다는데.. 알고리즘 잡스에서 이 코드로 실행 했을 때는 틀리게 나온다. 

2. 여기서는  map[i][j] = Math.min(map[i-1][j], map[i][j-1])+1; 이렇게 해야지 맞게 된다.. 이유를 잘 모르겠다..

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        String a = sc.nextLine();
        String b = sc.nextLine();
        int asize = a.length();
        int bsize = b.length();
        int map[][] = new int[asize + 1][bsize + 1];

        for (int i = 0; i <= asize; i++)
            map[i][0] = i;
        for (int j = 0; j <= bsize; j++)
            map[0][j] = j;

        for (int i = 1; i <= asize; i++) {
            for (int j = 1; j <= bsize; j++) {
                if(a.charAt(i-1)==b.charAt(j-1))
                    map[i][j] = map[i-1][j-1];
                else
                    map[i][j] = Math.min(map[i-1][j], map[i][j-1])+1;
                    //map[i][j] = Math.min(map[i-1][j-1], Math.min(map[i-1][j], map[i][j-1]))+1;
                
            }

        }
        System.out.println(map[asize][bsize]);

    }

}