편집 거리

📌문제

두개의 문자열 A,B가 주어졌을 때 문자열 A를 편집하여 문자열 B로 만들고자 한다. 문자열 A를 편집할 때는 다음 세 연산 중 한번에 하나씩 선택하여 이용할 수 있다.

1. 삽입: 특정한 위치에 하나의 문자를 삽입

2. 삭제: 특정한 위치에 있는 하나의 문자를 삭제

3. 교체: 특정한 위치에 있는 하나의 문자를 다른 문자로 교체

 

이때 편집 거리란 문자열 A를 편집하여 문자열 B로 만들기 위해 사용한 연산의 수를 의미한다. 문자열 A를 B로 만드는 최소 편집 거리를 계산하는 프로그램을 작성하시오.

 

📌풀이

최소 편집 거리를 담을 2차원 테이블

1. 행과 열에 해당하는 문자가 서로 같다면, 왼쪽 위에 해당하는 수를 그대로 대입

2. 행과 열에 해당하는 문자가 서로 다르다면, 왼쪽(삽입), 위쪽(삭제), 왼쪽 위(교체)에 해당하는 수 중 가장 작은 수에 1을 더해 대입

 

📌코드

def edit_dist(str1, str2):
    n = len(str1)
    m = len(str2)

    # 2차원 DP테이블 초기화
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    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][j - 1], dp[i - 1][j], dp[i - 1][j - 1])
    return dp[n][m]


str1 = input()
str2 = input()

print(edit_dist(str1, str2))

 

📌참고

https://g.co/kgs/eyd5SSd

이것이 취업을 위한 코딩 테스트다 with 파이썬