[백준/BOJ] gold1 - 7620번 편집 거리 (Python) / 메모리 초과

▶7620 - 편집 거리

▶문제

문자열이 주어졌을 때, 이 문자열을 다른 문자열로 바꾸는 편집 스크립트를 작성하려고 한다. 편집 스크립트에서 사용할 수 있는 명령은 아래와 같이 총 네 가지가 있다.

• 추가 ('a'): 한 글자를 출력한다. 이 명령은 입력 문자열을 건드리지 않는다.
• 삭제 ('d'): 한 글자를 삭제한다. 이 명령은 입력 문자열에서 맨 앞 글자를 삭제하고, 아무것도 출력하지 않는다.
• 수정 ('m'): 한 글자를 수정한다. 즉, 입력 문자열에서 맨 앞 글자를 삭제하고, 바꾼 글자를 출력한다.
• 복사 ('c'): 한 글자를 복사한다. 입력에서 맨 앞 글자를 삭제하고, 삭제한 그 글자를 출력한다.

가장 짧은 편집 스크립트란, 추가, 삭제, 수정을 가장 적게 사용한 스크립트이다.

두 문자열이 주어졌을 때, 첫 번째 문자열을 두 번째 문자열로 바꾸는 가장 짧은 편집 스크립트를 작성하는 프로그램을 작성하시오. 

 

▶입력

두 문자열이 한 줄에 하나씩 주어진다. 각 문자열은 영문 알파벳과 숫자로만 이루어져 있으며, 길이는 1보다 크거나 같고, 17000보다 작거나 같다.

 

▶출력

가장 짧은 편집 스크립트를 출력한다. 한 명령을 한 줄에 하나씩 출력하며, 문제의 괄호에 나와있는 (a, d, m, c)중 하나를 출력하고, 그 명령을 수행하는 데 사용한 글자를 출력한다. (출력할 글자나 삭제할 글자)

가장 짧은 편집 스크립트가 여러 가지인 경우에는 아무거나 출력하면 된다.

 

▶예제

 

▶풀이

일단 최소 작업 회수를 구해야 한다. 표를 그려서 해보면 쉽게 알 수 있다.

표의 가장 기본값은 아래의 표와 같아진다.

	-	x	a	b	z	d	e	y
-	0	1	2	3	4	5	6	7
a	1
b	2
c	3
d	4
e	5

표를 하나씩 채워가야 하는데, 위쪽의 값 + 1, 왼쪽의 값 + 1

또는 그 문자가 같을 땐 왼쪽 위 대각선 값, 그 문자가 다를 땐 왼쪽 위 대각선 값 + 1

이 중에서 min값이 그 칸의 값이 된다.

 

이 수식은 아래와 같은 코드로 나타내면 아래와 같아진다.

diff함수는 직접 만든 함수이다. 문자가 같을 땐 return 0, 다를 땐 return 1해 주는 함수이다.

dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1,
               dp[i - 1][j - 1] + diff(a[i - 1], b[j - 1]))

  이런 방식으로 표를 채우면 아래와 같아진다.

	-	x	a	b	z	d	e	y
-	0	1	2	3	4	5	6	7
a	1	1	1	2	3	4	5	6
b	2	2	2	1	2	3	4	5
c	3	3	3	2	2	3	4	5
d	4	4	4	3	3	2	3	4
e	5	5	5	4	4	3	2	3

최종 값은 3이 되고, 돌아갈 땐 그 문자가 같은지 다른지, 주변에 min값은 무엇인지 찾는다.

• dp[i][j] = dp[i - 1][j - 1]일 때 ‘복사’
• dp[i][j] = dp[i - 1][j - 1] + 1일 때 ‘수정’
• dp[i][j] = dp[i - 1][j] + 1일 때 ‘추가’
• dp[i][j] = dp[i][j - 1] + 1일 때 ‘삭제’

위로 돌아가면서 나오는 값을 result에 넣고 출력할 때 역순으로 출력한다.

def diff(m, n):
    if m == n:
        return 0
    else:
        return 1


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

for i in range(1, la + 1):
    for j in range(1, lb + 1):
        dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1,
                       dp[i - 1][j - 1] + diff(a[i - 1], b[j - 1]))

result = []
while True:
    if la == 0 and lb == 0:
        break
    position = min(dp[la - 1][lb - 1], dp[la][lb - 1], dp[la - 1][lb])
    if position == dp[la][lb]:
        result.append("c " + b[lb - 1])
        la -= 1
        lb -= 1
    elif position == dp[la - 1][lb]:
        result.append("d " + a[la - 1])
        la -= 1
    elif position == dp[la][lb - 1]:
        result.append("a " + b[lb - 1])
        lb -= 1
    elif position == dp[la - 1][lb - 1]:
        result.append("m " + a[la - 1])
        la -= 1
        lb -= 1

for re in result[::-1]:
    print(re)

python으로도 pypy로도 제출하니까 일단 틀렸다고 뜬다.

알고리즘 1 시간에 했던 문제라서 코드는 틀렸을 리 없고...

그래서 찾아보니까 python3로도 pypy3로도 제출해서 맞춘 사람이 없다.

 

코드는 더 고민해보았지만... 메모리까지 완벽하게 해서 정답을 맞히기엔 아직 내가 역부족인 것 같다.

나중에 다시 풀어보고 정답이 나오면 수정하거나 글을 새로 올려야겠다.