forked from 2ByungJun/python-for-coding-test
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path6.java
More file actions
50 lines (40 loc) Β· 1.55 KB
/
6.java
File metadata and controls
50 lines (40 loc) Β· 1.55 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import java.util.*;
public class Main {
static String str1;
static String str2;
// μ΅μ νΈμ§ 거리(Edit Distance) κ³μ°μ μν λ€μ΄λλ―Ή νλ‘κ·Έλλ°
static int editDist(String str1, String str2) {
int n = str1.length();
int m = str2.length();
// λ€μ΄λλ―Ή νλ‘κ·Έλλ°μ μν 2μ°¨μ DP ν
μ΄λΈ μ΄κΈ°ν
int[][] dp = new int[n + 1][m + 1];
// DP ν
μ΄λΈ μ΄κΈ° μ€μ
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 (str1.charAt(i - 1) == str2.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]));
}
}
}
return dp[n][m];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str1 = sc.next();
String str2 = sc.next();
// μ΅μ νΈμ§ 거리 μΆλ ₯
System.out.println(editDist(str1, str2));
}
}