[실전 문제] 두 문자열 사이의 거리

1. 문제

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

---

입력

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

출력

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

예제 입력

abcabcd
abccabc

예제 출력

2

 

 

 

2. 풀이

이 문제는 대표적인 편집 거리 알고리즘 문제이다.

 

예를 들어, 두 문자열이 주어졌을 때,

a

b

 a를 삭제하고 b를 삽입하던, b를 삭제하고 a를 삽입하던 행동이 2번 이루어진다.

 

ab

ba

ab에서 a를 삭제하고 뒤에 a를 삽입하던, ba에서 b를 삭제하고 뒤에 b를 삽입하던 행동이 2번 이루어진다.

 

abc

abd

abc에서 c를 삭제하고 d를 삽입하던, abd에서 d를 삭제하고 뒤에 c를 삽입하던 행동이 2번 이루어진다.

 

ab

c

ab에서 a와 b를 삭제하고 c를 삽입하던, c에서 c를 삭제하고 a와 b를 삽입하던 행동이 3번 이루어진다.

 

이를 하나의 표로 정리해보면 패턴을 찾을 수 있다.

비교하는 문자가 같을 경우 대각선의 값을 그대로 가져오고 비교하는 문자가 다를 경우, 주위(왼쪽, 위)의 값중 최소값에 1을 더해준 값이 들어가는 것을 확인할 수 있다.

 

이를 코드로 작성하면 다음과 같다.

import java.io.*;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {

        String s1 = br.readLine();
        String s2 = br.readLine();

        int[][] arr = new int[s1.length() + 1][s2.length() + 1];

        for(int i = 0; i <= s1.length(); i++) {
            arr[i][0] = i;
        }
        for(int j = 0; j <= s2.length(); j++) {
            arr[0][j] = j;
        }

        for(int i = 1; i <= s1.length(); i++) {
            for(int j = 1; j <= s2.length(); j++) {
                if(s1.charAt(i-1) == s2.charAt(j-1)) {
                    arr[i][j] = arr[i-1][j-1];
                } else {
                    arr[i][j] = Math.min(arr[i-1][j], arr[i][j-1]) + 1;
                }
            }
        }
        bw.write(arr[s1.length()][s2.length()] + "");
        br.close();
        bw.flush();
        bw.close();
    }
}