[이것이 코딩테스트다] #36 편집 거리

• 본 문제는 <이것이 코딩테스트다 with python (한빛미디어, 나동빈 저)> 에서 가져왔습니다.

 

문제

 

풀이

먼저, 두 개의 문자열을 비교하는 것이기 때문에 dp 테이블을 2차원으로 만들어야한다.

 

dp[i][j] --> A의 i번째까지의 문자열을 B의 j번째까지의 문자열로 바꿀 때의 편집 거리

 

간단하게, 예시에 나오는 "cat" 과 "cut" 으로 dp 테이블을 만들면 다음과 같다. 

	c	u	t
c	0	1	2
a	1	1	2
t	2	2	1

(1, 1): "c"에서 "c"로 갈 때 필요한 연산 수 = 0

(1, 2): "c"에서 "cu"로 갈 때 필요한 연산 수 = 1

(1, 3): "c"에서 "cut"로 갈 때 필요한 연산 수 = 2

(2, 1): "ca"에서 "c"로 갈 때 필요한 연산 수 = 1

...

(3, 3): "cat"에서 "cut"로 갈 때 필요한 연산수 = 1

 

이제 이 dp 테이블을 보면서 점화식을 만들면 된다.

가장 먼저 생각해야 될 것은 글자가 같냐 / 같지 않냐로 나눈 것이다.

 

예를 들어, 'ca'에서 'cu'로 갈 때 1개의 연산이 필요한데, 'cat'에서 'cut'로 갈 때 추가적인 글자 t가 같기 때문에 더 이상의 연산이 필요없기 때문이다.  즉,  'ca' -> 'cu' 에 필요한 연산이나, 'cat' -> 'cut' 에 필요한 연산이 같다. 때문에 왼쪽 위칸의 연산 수를 그대로 가져오면 된다.

 

만약 같지 않다면?

이전의 연산 (즉, 왼쪽 위칸 / 왼쪽 칸 /  윗칸) 중 최솟값에 +1 을 해주면 된다. 

 

이를 코드로 정리하면 다음과 같다.

 

a = input()
b = input()

# initialize the dp table

dp = [[0]*(len(b)) for _ in range(len(a))]
print(dp)

if a[0] == b[0]:
    dp[0][0] = 0
else:
    dp[0][0] = 1

for i in range(1, len(a)):
    dp[i][0] = dp[0][0] + i
for j in range(1, len(b)):
    dp[0][j] = dp[0][0] + j

# solve 
for i in range(1, len(a)):
    for j in range(1, len(b)):
        if a[i] == b[j]:
            dp[i][j] = dp[i-1][j-1]
        else:
            dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1

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

푸는 코드보다 dp 테이블 초기화 시키는 코드가 더 긴건.... 어쩔 수 없는 거겠징..?