문제
두 개의 문자열 A와 B가 주어졌을 때, 문자열 A를 편집하여 문자열 B로 만들고자 한다.
1. 삽입(Insert) : 특정한 위치에 있는 하나의 문자를 삽입
2. 삭제(Remove) : 특정한 위치에 있는 하나의 문자를 삭제
3. 교체(Replace) : 특정한 위치에 있는 하나의 문자를 다른 문자로 교체
이때 편집 거리란 문자열 A를 편집하여 문자열 B로 만들기 위해 사용한 연산의 수를 의미함, A를 B로 만드는 최소 편집 거리를 계산하는
프로그램을 작성하시오.
입력
두 문자열 A와 B가 한 줄에 하나씩 주어짐
출력 : 최소 편집 거리를 출력
이 문제는 2차원 테이블과 점화식을 이용하여 문제를 해결할 수 있다.
<1> : su--> sa 만든 후에 뒤에 붙어 있는 n을 t로 교체 : <1> + 교체 비용 1
<2> : sun --> sa 만든 후에 뒤에 t를 삽입 : <2> + 삽입 비용 1
<3> : su --> sat 를 만드는 비용과 비교하였을 때, sun --> sat를 만드는 비용은 1개를 삭제하는 비용만큼 더 든다 : <3> + 삭제 비용 1
<4> : s --> sat를 만드는 비용과 su --> satu를 만드는 비용은 양쪽에 동일하게 u가 더해진 것이므로 동일하다
따라서 a[i] == b[i]일 경우 table[i-1][j-1] == table[i][j]l이다!
len(A) == len(B)의 기준이 되는 선으로 부터
좌측 방향으로 가면 A의 길이가 늘어나므로 (A^->B) : A를 삭제하여 B를 만드는 것이 됨 == <3>
우측 방향으로 가면 B의 길이가 늘어나므로 (A->B^) : A에 삽입하여 B를 만드는 것이 됨 == <2>
우측 아래 대각선 뱡향으로 가면 A와 B의 길이가 동일하므로 : A를 교체하여 B를 만드는 것이 됨 == <1>
따라서 정리하면 A --> B를 만들 때
1. 두 문자가 같은 경우 (a[i] == b[j])
table[i][j] == table[i-1][j-1]
2. 두 문자가 다를 경우 (a[i] != b[j])
table[i][j] = 1 + min(table[i][j-1], table[i-1][j], table[i-1][j-1])
풀이
# 16-36) 편집 거리
a = list(input()); a.insert(0, "*")
b = list(input()); b.insert(0, "*")
table = [[None for _ in range(len(b))] for _ in range(len(a))]
for i in range(len(a)): table[i][0] = i
for j in range(len(b)): table[0][j] = j
for i in range(1, len(a)):
for j in range(1, len(b)):
if a[i-1] == b[j-1]:
# 이 경우 table[i-1][j-1]에서 동일한 문자 1개씩만을 추가하면 되므로 편집 거리에는 변화가 없다
table[i][j] = table[i-1][j-1]
else:
table[i][j] = min(table[i-1][j], table[i][j-1], table[i-1][j-1]) + 1
print(table[len(a)-1][len(b)-1])