백준 15483 : 최소 편집

https://www.acmicpc.net/problem/15483

15483번: 최소 편집

[ 문제풀이 ]

편집 거리 알고리즘으로 유명한 문제이다. dp 테이블을 다음과 같이 정의하자

dp[i][j] : A.substring(0,i+1)으로 B.substring(0,j+1)를 편집하는 최소횟수

 

만약 A의 i번째 문자와 B의 j번째 문자가 같다면 dp[i][j]의 값은 무엇일까? 두 문자열의 마지막 문자가 같기 때문에 마지막 문자에 관한 편집은 할 필요가 없다는 것을 알 수 있다.

즉, 마지막 문자가 없는 상태인 A의 i-1번째까지의 문자열로 B의 j-1번째 문자열을 만드는 최솟값인 dp[i-1][j-1]와 동일한 것을 알 수 있다.

 

그렇다면 A의 i번째 문자와 B의 j번째 문자가 다르다면 dp[i][j]의 값은 무엇일까? 마지막 문자가 다르기 때문에 기존의 최솟값에서 문자를 삽입, 삭제, 교체 중 하나의 연산을 수행해야 한다는 것을 알 수 있다.

잘 생각해보면 dp[i-1][j-1] 값에는 서로의 마지막 문자를 제외한 문자열을 만드는 최솟값이 저장되어있다. 따라서 dp[i-1][j-1] 상태에서 A의 i번째문자를 B의 j번째문자로 교체한다면 j까지의 B문자열을 만들 수 있을 것이다.

또한, dp[i-1][j]에는 i-1번째까지의 A문자열로 j번째까지의 B문자열을 만든 최솟값이 저장되어있다. 이미 B문자열을 만들었기 때문에 A의 i번째 문자는 필요가 없으므로 삭제해야 B문자열을 유지할 수 있다.

마지막으로 dp[i][j-1]에는 i번째까지의 A문자열로 j-1번째까지의 B문자열을 만든 최솟값이 저장되어 있으며, 이 상태에서 B의 j번째 문자를 삽입한다면 j까지의 B문자열을 만들 수 있다.

 

따라서 도출해낸 점화식은 다음과 같다.

if A.charAt(i) == B.charAt(j)
    then dp[i][j] = dp[i - 1][j - 1];
else
    then dp[i][j] = min(dp[i - 1][j], dp[i][j - 1] dp[i - 1][j - 1]) + 1;

 

마지막으로 인덱스 처리를 쉽게 해주기 위해 A, B의 첫 번째 문자부터가 아닌 공백상태부터 시작하도록 해준다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))){
			String s1 = br.readLine();
			String s2 = br.readLine();
			int s1l = s1.length();
			int s2l = s2.length();
			/**
			 * dp[i][j] : s1.substring(0,i+1)으로 s2.substring(0,j+1)를 편집하는 최소횟수
			 */
			int[][] dp = new int[s1l + 1][s2l + 1];
			
			for (int i = 0; i <= s1l; ++i) dp[i][0] = i;
			for (int i = 0; i <= s2l; ++i) dp[0][i] = i;
			for (int i = 1; i <= s1l; ++i) {
				for (int j = 1; j <= s2l; ++j) {
					if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
						dp[i][j] = dp[i - 1][j - 1];
					} else {
						dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
					}
				}
			}
			bw.write(dp[s1l][s2l] + "\n");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}