[엘리스] 두 문자열 사이의 거리

두 문자열 사이의 거리

두 문자열 s1, s2가 주어진다. 이제 s1에서 문자 하나를 추가하거나 제거할 수 있으며, 이를 반복함으로써 s2를 얻고싶다고 하자. 예를 들어, s1 = “abc”, s2 = “bdcf” 라고 하면, s1에서 a를 제거하고 d를 추가, 그리고 f를 추가하면 s2를 얻을 수 있다. 즉, 다음과 같은 경로로 s1에서 s2를 얻을 수 있다.

 

$“abc” -> “bc” -> “bdc” -> “bdcf”$

 

두 문자열 s1, s2 사이의 거리란, s1에서 s2를 만들기 위해 필요한 문자 삽입, 삭제 횟수의 최소값으로 정의된다. 예를 들어, s1 = “abc”, s2 = "bdcf"라면, 두 문자열의 거리는 3이다. 왜냐하면, s1에서 문자의 추가 및 삭제를 3번 하면 s2를 얻을 수 있기 때문이며, 이보다 더 적은 연산을 통해서는 s2를 얻을 수 없다.

 

두 문자열이 주어질 때, 두 문자열 사이의 거리를 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에 문자열 s1, 두 번째 줄에 문자열 s2가 주어진다. 문자열의 길이는 2000을 넘지 않는다.

출력

두 문자열 사이의 거리를 출력한다.

입력 예시

abc
bdcf

출력 예시

3

풀이

• abc, bdcf의 최대 공통 부분의 수열의 길이를 계산
• LCS : "bc"
  • abc에서 LCS를 제외한 a를 변경해야 함
  • bcdf에서 LCS를 제외한 d,f를 변경해야 함
  • 즉, (len(abc) - LCS) + (len(bcdf) - LCS) = len(abs) + len(bcdf) - 2LCS

import sys

def LCS(s1, s2):
    '''
    1. 마지막이 겹치는 경우 
    - T[i][j] = T[i-1][j-1] + 1
    2. 그렇지 않은 경우 
    - max(T[i-1][j], T[i][j-1])
    '''

    T = [[0 for i in range(len(s2)+1)] for i in range(len(s1)+1)]

    for i in range(1, len(s1)+1):
        for j in range(1, len(s2)+1):
            if s1[i-1] == s2[j-1] :
                T[i][j] = T[i-1][j-1] + 1
            else :
                T[i][j] = max(T[i-1][j], T[i][j-1])
    return T[len(s1)][len(s2)]

def strDistance(s1, s2) :

    '''
    ((첫번째 문자열의 길이) - LCS) + ((두번째 문자열의 길이) - LCS)

    '''
    lcs = LCS(s1, s2)
    return len(s1) + len(s2) - 2 * lcs

def main():
    '''
    이 부분은 수정하지 마세요.
    '''

    s1 = input()
    s2 = input()

    print(strDistance(s1, s2))

if __name__ == "__main__":
    main()

 

 

출처 : 엘리스 아카데미, https://academy.elice.io/learn