편집 거리

편집 거리

문제 설명

A와 B의 두 개의 문자열이 주어졌을 때 삽입, 삭제, 교체의 방법으로 A를 B로 만들때까지 몇 번의 연산을 하는지 출력하는 문제이다.

해결방법

A = sunday, B = saturday 를 기준으로 dp테이블을 그림으로 확인해 보겠다

1. 같은 문자일때는 dp[i-1] [j-1] 의 숫자를 그대로 가져온다.

0	s	a	t	u	r	d	a	y
s	0
u
n
d
a
y

2. → 은 삽입 연산의 수행이다.

• s로 sa 를 만들기 위해서는 ‘a’ 를 삽입하면 된다.

• s로 sat를 만들기 위해서는 ‘a’,’t’를 삽입하면 된다.

0	s	a	t	u	r	d	a	y
s	0	1	2	3	4	5	6	7
u
n
d
a
y

4. ↘ 은 교체 연산의 수행이다.

• su 를 sa 로 만드려면 ‘u’를 ‘a’로 교체하면 된다.

0	s	a	t	u	r	d	a	y
s	0	1	2	3	4	5	6	7
u	1	1
n	2
d	3
a	4
y	5

3. ↓ 은 삭제 연산의 수행이다.

• su 를 s 로 만드려면 ‘u’를 삭제하면 된다.
• sun을 s로 만드려면 ‘u’, ‘n’를 삭제하면 된다.

0	s	a	t	u	r	d	a	y
s	0	1	2	3	4	5	6	7
u	1
n	2
d	3
a	4
y	5

5. 수행결과 dp[-1][-1] 에 총 몇번의 연산을 수행했는지 알 수 있다.

• 같은 문자일때는 연산할 필요가 없으므로 dp[i-1] [j-1] 의 숫자를 그대로 가져오고,
• 그 외에는 dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1 를 순차적으로 수행하면 된다.

0	s	a	t	u	r	d	a	y
s	0	1	2	3	4	5	6	7
u	1	1	2	2	3	4	5	6
n	2	2	2	3	3	4	5	6
d	3	3	3	3	4	3	4	5
a	4	3	4	4	4	4	3	4
y	5	4	4	5	5	5	4	3

INF = int(1e9)

A = input()
B = input()

dp = [[INF for _ in range(len(B)+1)] for _ in range(len(A)+1)]
dp[0][0] = 0

for i in range(len(B)):
    dp[0][i+1] = ord(B[i]) # 영문자는 아스키코드로 입력해준다

for i in range(len(A)):
    dp[i+1][0] = ord(A[i]) # 영문자는 아스키코드로 입력해준다

for i in range(1, len(A) + 1):
    for j in range(1, len(B) + 1):
        if dp[0][j] == dp[i][0]:
            dp[i][j] = dp[i-1][j-1]
        else:
            dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1

print(dp[-1][-1])