두 개의 문자열 A, B가 주어졌을 때 두 문자열이 얼마나 유사한 지를 알아낼 수 있는 알고리즘입니다. 그러니까, 문자열 A가 문자열 B와 같아지기 위해서는 몇 번의 연산(DELETE / INSERT / REPLACE)을 진행해야 하는 지 계산할 수 있습니다.
두 문자열 s1 , s2 가 주어진다면 s1을 s2로 만드는데 필요한 최소한의 연산을 구하라
s1 = “sunday” / s2 = “saturday”
분석)
정리) 분석 단계에서 분석한 1,2 번의 요소를 공식으로 표현하면 다음과 같다.
공식에 따라 최종적으로 배열에 표현한 값은 다음과 같아지며 두 문자를 동일하게 만들기 위해 필요한 최소한의 비용은 배열의 가장 마지막 d[n][m]의 값이 된다.
| … | . | S | U | N | D | A | Y |
|---|---|---|---|---|---|---|---|
| . | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| S | 1 | 0 | 1 | 2 | 3 | 4 | 5 |
| A | 2 | 1 | 1 | 2 | 3 | 3 | 4 |
| T | 3 | 2 | 2 | 2 | 3 | 4 | 4 |
| U | 4 | 3 | 2 | 3 | 3 | 4 | 5 |
| R | 5 | 4 | 3 | 3 | 4 | 4 | 5 |
| D | 6 | 5 | 4 | 4 | 3 | 4 | 5 |
| A | 7 | 6 | 5 | 5 | 4 | 3 | 4 |
| Y | 8 | 7 | 6 | 6 | 5 | 4 | 3* |
초기 배열 설정에서 arr[i][0] , arr[0][j]는 배열의 길이 -1 만큼 i++ / j++ 반복 연산을 해주어야 한다.
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String s1= sc.nextLine();
String s2 = sc.nextLine();
int n = s1.length();
int m = s2.length();
int[][] dp = new int[n+1][m+1];
for (int i = 1; i <= n; i++) {
dp[i][0] = i;
}
for (int j = 1; j <= m; j++) {
dp[0][j] = j;
}
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(s1.charAt(i-1)==s2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1];
}else{
dp[i][j] = 1 + Math.min(dp[i][j - 1], Math.min(dp[i - 1][j], dp[i - 1][j - 1]));
}
}
}
for(int i=1; i<n; i++){
for(int j=1; j<m; j++) {
System.out.print(dp[i][j] + " ");
}
System.out.println();
}
}
}