[Python] 편집거리

문제

• 두 개의 문자열 A와 B가 주어졌을 때, 문자열 A를 편집하여 문자열 B로 만들고자 합니다.
• 문자열 A를 편집할 때는 다음의 세 연산 중에서 한 번에 하나씩 선택하여 이용할 수 있습니다.
  • 삽입(Insert): 특정한 위치에 하나의 문자를 삽입합니다.
  • 삭제(Remove): 특정한 위치에 있는 하나의 문자를 삭제합니다.
  • 교체(Replace): 특정한 위치에 있는 하나의 문자를 다른 문자로 교체합니다.
• 이때 편집 거리란 문자열 A를 편집하여 문자열 B로 만들기 위해 사용한 연산의 수를 의미합니다.
• 문자열 A를 문자열 B로 만드는 최소 편집 거리를 계산하는 프로그램을 작성하세요.
• 예를 들어 "sunday"와 "saturday"의 최소 편집 거리는 3입니다.

입력

• 두 문자열 A와 B가 한줄에 하나씩 주어집니다.
• 각 문자열은 영문 알파벳으로만 구성되어 있으며 , 각 문자열의 길이는 1보다 크거나 같고, 5,000보다 작거나 같습니다.

출력

• 최소 편집 거리를 출력합니다.

입력 예시

cat
cut

출력 예시

3

문제 풀이

• 최소 편집거리를 담을 2차원 테이블을 초기화한 뒤엥, 최소 편집 거리를 계산해 테이블에 저장하는 과정으로 문제 해결할 수 있다.
• 점화식은 아래와 같다.

# 두 문자가 같은 경우
dp[i][j] = dp[i - 1][j - 1]

# 두 문자가 다른 경우
dp[i][j] = 1 + min(dp[i -1][j], dp[i][j - 1], dp[i - 1][j - 1])

• 이를 풀어서 보면, 행과 열에 해당하는 문자가 서로 같다면 왼쪽 위에 해당하는 수를 그대로 대입(편집 필요 없으므로)
• 행과 열에 해당하는 문자가 서로 다르다면, 왼쪽(삽입), 위쪽(삭제), 왼쪽 위(교체)에 해당하는 수 중에서 가장 작은 수에 1을 더해 대입
• 이렇게 차례대로 탐색했을 때, 테이블의 가장 오른쪽 아래에 있는 값이 구하고자 하는 최소 편집 거리가 된다.

코드

str1 = input()
str2 = input()
def str_district(str1, str2):
    n = len(str1)
    m = len(str2)

    # 문자열 탐색 위한 dp테이블 초기화
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    # dp테이블에 초기 값 넣어주기
    for i in range(1, n + 1):
        dp[i][0] = i
    for j in range(1, m + 1):
        dp[0][j] = j

    # 최소 편집거리 계산
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            # 문자가 같다면 해당하는 수 바로 대입
            if str1[i - 1] == str2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            # 문자가 다르다면 3가지 경우 중 최솟값 찾기
            else:
                dp[i][j] = 1 + min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j])
    return dp[n][m]

print(str_district(str1, str2))