알고리즘 스터디 - 백준 7620번 : 편집 거리 (feat. Python)

문제 해석

1. 문자열 2개가 주어진다

2. 편집 과정에서 할 수 있는 명령은 아래와 같다.

   • 추가 ('a') : 한 글자를 출력하고 입력 문자열을 건드리지 않는다.
   • 삭제 ('d') : 입력 문자열 맨 앞 한 글자를 삭제하고 아무 것도 출력하지 않는다.
   • 수정 ('m') : 입력 문자열 맨 앞 한 글자를 삭제하고 다른 글자로 바꿔 출력한다.
   • 복사 ('c') : 맨 앞 글자를 삭제하고 삭제한 그 글자를 출력한다.

3. 첫 번째 문자열을 두 번째 문자열로 바꾸는 가장 짧은 편집 스크립트를 작성해야 함

어떤 알고리즘을 써야할까?

1. dp를 이용하여 편집 거리를 구함
2. 가장 작은 수부터 되돌아가면서 배열의 저장
3. 배열의 저장한 것을 반대로 출력

알고리즘 코드

이 문제 Python3, Pypy 둘다 적용해도 풀리지 않는다. 메모리 초과가 나타나고 Python으로 풀었던 사람이 아예 없다. 그래도 일단 테케는 통과했으니 이 문제는 여기까지,,

n = input()
m = input()

dp = [[0] * (len(n) + 1) for _ in range(len(m) + 1)]

for i in range(1, len(m) + 1):
    dp[i][0] = i
    
for j in range(1, len(n) + 1):
    dp[0][j] = j
    
for i in range(1, len(m) + 1):
    for j in range(1, len(n) + 1):
        if m[i-1] == n[j-1]:
            # 두 문자가 같은 경우, 추가 연산이 필요하지 않으므로 (i-1, j-1)에서 가져온다. 'c' 
            dp[i][j] = dp[i-1][j-1]
        else:
            # 두 문자가 다른 경우, (교체 'm'| 추가 'a' | 삭제 'd') 세 연산 중 cost가 가장 적은 것을 기록한다. 
            dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
    
len_n = len(n)
len_m = len(m)

trace_array = []

while len_n > -1 and len_m > -1:
    index_pos = min(dp[len_m-1][len_n], dp[len_m-1][len_n-1], dp[len_m][len_n-1])
    if index_pos == dp[len_m][len_n]:
        trace_array.append("c " + n[len_n-1])
        len_n -= 1
        len_m -= 1
    else:
        if index_pos == dp[len_m][len_n-1]:
            trace_array.append("d " + n[len_n-1])
            len_n -= 1
        elif index_pos == dp[len_m-1][len_n-1]:
            trace_array.append("m " + m[len_m-1])
            len_n -= 1
            len_m -= 1
        else:
            trace_array.append("a " + m[len_m-1])
            len_m -= 1

for index in range(len(trace_array)-2, -1, -1):
    print(trace_array[index])