[백준] 15483번: 최소편집

문제

[백준] 15483번: 최소편집

분석

문자열 A, B가 주어졌을 때, A에서 B가 되는 최소 편집 횟수를 구하는 문제이다.
연산 종류는 다음과 같다.

삽입: A의 한 위치에 문자 하나를 삽입한다.
삭제: A의 문자 하나를 삭제한다.
교체: A의 문자 하나를 다른 문자로 교체한다.

이 문제는 문자열 앞부분부터 한 글자씩 범위를 넓혀가며 최소비용을 저장하면 된다.
i: 문자열 A의 앞에서부터 i개 글자까지의 부분 문자열
j: 문자열 B의 앞에서부터 j개 글자까지의 부분 문자열
dp[i][j]: A의 i글자를 B의 j글자로 변환하는 데 드는 최소 편집 비용

경우를 나눠보면 교체, 삭제, 삽입이 있다.
교체: 이전 상태 dp[i-1][j-1]
A[i]와 B[j]가 같을 때는 그대로 dp[i-1][j-1]이 되어 추가 비용이 0이다.
다를 때는 교체 작업이므로 +1이 된다.
삭제: 이전 상태 dp[i-1][j]
A의 i번째 글자만 삭제하는 경우 삭제 작업 +1이 된다.
삽입: 이전 상태 dp[i][j-1]
B의 j번째 글자를 삽입하는 경우 삽입 작업 +1이 된다.

위의 경우 중 가장 작은 값을 취하면서 dp 테이블을 채워나간다.

초기값:
dp[i][0]는 전부 삭제 비용이므로 A의 부분 문자열 만큼인 i로 초기화 해주고,
dp[0][j]는 전부 삽입 비용이므로 B의 부분 문자열 만큼인 j로 초기화 해준다.

시간 복잡도는 반복문 두 번으로 O(두 문자열 길이 곱)이 된다.

코드

해결언어 : Java

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	static char[] A, B;
	static int[][] dp;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		A = br.readLine().toCharArray();
		B = br.readLine().toCharArray();
		dp = new int[A.length + 1][B.length + 1];
		for (int i = 1; i <= A.length; i++)
			dp[i][0] = i;
		for (int j = 1; j <= B.length; j++)
			dp[0][j] = j;
		for (int i = 1; i <= A.length; i++) {
			for (int j = 1; j <= B.length; j++) {
				int cost = A[i - 1] != B[j - 1] ? 1 : 0;
				dp[i][j] = Math.min(dp[i - 1][j - 1] + cost, Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
			}
		}
		System.out.println(dp[A.length][B.length]);
		br.close();
	}

}